{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Islands"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numIslands"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #岛屿数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个由 <code>'1'</code>（陆地）和 <code>'0'</code>（水）组成的的二维网格，请你计算网格中岛屿的数量。</p>\n",
    "\n",
    "<p>岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。</p>\n",
    "\n",
    "<p>此外，你可以假设该网格的四条边均被水包围。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [\n",
    "  [\"1\",\"1\",\"1\",\"1\",\"0\"],\n",
    "  [\"1\",\"1\",\"0\",\"1\",\"0\"],\n",
    "  [\"1\",\"1\",\"0\",\"0\",\"0\"],\n",
    "  [\"0\",\"0\",\"0\",\"0\",\"0\"]\n",
    "]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [\n",
    "  [\"1\",\"1\",\"0\",\"0\",\"0\"],\n",
    "  [\"1\",\"1\",\"0\",\"0\",\"0\"],\n",
    "  [\"0\",\"0\",\"1\",\"0\",\"0\"],\n",
    "  [\"0\",\"0\",\"0\",\"1\",\"1\"]\n",
    "]\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 <= m, n <= 300</code></li>\n",
    "\t<li><code>grid[i][j]</code> 的值为 <code>'0'</code> 或 <code>'1'</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-islands](https://leetcode.cn/problems/number-of-islands/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-islands](https://leetcode.cn/problems/number-of-islands/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"1\",\"1\",\"1\",\"1\",\"0\"],[\"1\",\"1\",\"0\",\"1\",\"0\"],[\"1\",\"1\",\"0\",\"0\",\"0\"],[\"0\",\"0\",\"0\",\"0\",\"0\"]]', '[[\"1\",\"1\",\"0\",\"0\",\"0\"],[\"1\",\"1\",\"0\",\"0\",\"0\"],[\"0\",\"0\",\"1\",\"0\",\"0\"],[\"0\",\"0\",\"0\",\"1\",\"1\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        def find(node):\n",
    "            while parent[node] != parent[parent[node]]:\n",
    "                parent[node] = parent[parent[node]]\n",
    "            return parent[node]\n",
    "        def union(n1, n2):\n",
    "            parent[find(n1)] = find(n2)\n",
    "        \n",
    "        res = [0]*len(positions)\n",
    "        parent = [i for i in range(m*n)]\n",
    "        land = [0 for i in range(m*n)]\n",
    "        for i, (r,c) in enumerate(positions):\n",
    "            idx = r*n + c \n",
    "            if land[idx]:\n",
    "                res[i] = res[i-1]\n",
    "                continue\n",
    "            land[idx] = 1\n",
    "            res[i] = res[i-1] + 1\n",
    "            for dx, dy in [(1,0), (0,1), (0,-1), (-1,0)]:\n",
    "                x, y = r+dx, c+dy\n",
    "                if m>x>=0<=y<n and land[x*n+y]==1 and find(idx)!=find(x*n+y):\n",
    "                    union(idx,x*n+y)\n",
    "                    res[i]-=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, m, n):  \n",
    "        self.parent = list(range(m * n))\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        self.parent[self.find(x)] = self.find(y)\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        uf = UnionFind(m, n)\n",
    "        island = [[0 for j in range(n)] for i in range(m)]\n",
    "        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        res = []\n",
    "        count = 0\n",
    "        for i, j in positions:\n",
    "            if island[i][j]:\n",
    "                res.append(count)\n",
    "                continue\n",
    "            island[i][j] = 1\n",
    "            count += 1\n",
    "            root1 = uf.find(i * n + j)\n",
    "            for dx, dy in directions:\n",
    "                x = i + dx\n",
    "                y = j + dy\n",
    "                if 0 <= x < m and 0 <= y < n and island[x][y]:\n",
    "                    root2 = uf.find(x * n + y)\n",
    "                    if root1 != root2:\n",
    "                        # 先root2后root1，否则root1在union之后会变\n",
    "                        uf.union(root2, root1)\n",
    "                        count -= 1\n",
    "            res.append(count)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # Union find. Time O(k*alpha(mn)) Space O(m*n)\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "        dsu = DSU(m * n)\n",
    "        lands = set()\n",
    "        res = []\n",
    "        for x, y in positions:\n",
    "            # if land already added, just repeat the last answer\n",
    "            if (x, y) in lands:\n",
    "                res.append(res[-1])\n",
    "                continue\n",
    "            lands.add((x, y))\n",
    "            last = res[-1] if res else 0\n",
    "            ancestors = set()\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n and (nx, ny) in lands:\n",
    "                    ancestors.add(dsu.find(nx * n + ny)) \n",
    "                    dsu.union(x * n + y, nx * n + ny)\n",
    "            # len(ancestors) groups are merged into 1 group\n",
    "            # so the number of islands is deducted by (len(ancestors) - 1)\n",
    "            res.append(last - (len(ancestors) - 1))\n",
    "        return res\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n):\n",
    "        self.pa = list(range(n))\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.pa[x] != x:\n",
    "            self.pa[x] = self.find(self.pa[x])\n",
    "        return self.pa[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        self.pa[self.find(x)] = self.find(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "\n",
    "\n",
    "        def find(x):\n",
    "            while parent[x]!=x:\n",
    "                y = parent[parent[x]]\n",
    "                parent[x] = y \n",
    "                x = y \n",
    "            return x \n",
    "        \n",
    "\n",
    "        def union(x,y):\n",
    "            p,q = find(x),find(y)\n",
    "            if p!=q:\n",
    "                if p>q:\n",
    "                    p,q = q,p \n",
    "                parent[q] = p \n",
    "            return \n",
    "\n",
    "        n1 = len(positions)\n",
    "        res = [0]*n1 \n",
    "        parent = [-1]*(m*n) \n",
    "        visited = set()\n",
    "\n",
    "        for i in range(n1):\n",
    "            x,y = positions[i]\n",
    "            z = x*n+y\n",
    "            parent[z] = z \n",
    "            if z in visited:\n",
    "                res[i] = res[i-1]\n",
    "                continue \n",
    "            res[i] = res[i-1]+1\n",
    "            \n",
    "\n",
    "            visited.add(z)\n",
    "\n",
    "            for dx,dy in [(1,0),(0,1),(-1,0),(0,-1)]:\n",
    "                if 0<=x+dx<m and 0<=y+dy<n and (x+dx)*n+y+dy in visited:\n",
    "                    if find(z)!=find((x+dx)*n+y+dy):\n",
    "                        union(z,(x+dx)*n+y+dy) \n",
    "                        res[i] -= 1\n",
    "        return res\n",
    "                    \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFindSet(object):\n",
    "    def __init__(self, data_list):\n",
    "        # initialize two dicts, one save the fathers of the nodes,\n",
    "        # the other save the size of the father node \n",
    "        # when initialization, the father of each node is itself \n",
    "        # all the sizes are set to be 1\n",
    "\n",
    "        self.father_dict = {}\n",
    "        self.size_dict = {}\n",
    "\n",
    "        for node in data_list:\n",
    "            self.father_dict[node] = node\n",
    "            self.size_dict[node] = 1\n",
    "\n",
    "    def find(self, node):\n",
    "        # use recursive way to search the root of the node \n",
    "        # when searching, put the node directly points to its root to let the tree shorter\n",
    "\n",
    "        father = self.father_dict[node]\n",
    "        if(node != father):\n",
    "            if father != self.father_dict[father]:    \n",
    "                # when optimize the tree, make sure the size of the father dict is corrcet \n",
    "                self.size_dict[father] -= 1\n",
    "            father = self.find(father)\n",
    "        self.father_dict[node] = father\n",
    "        return father\n",
    "\n",
    "    def is_same_set(self, node_a, node_b):\n",
    "        # set whether two nodes are in the same set, check whether the roots are the same\n",
    "        return self.find(node_a) == self.find(node_b)\n",
    "\n",
    "    def union(self, node_a, node_b):\n",
    "        # combine two sets \n",
    "        if node_a is None or node_b is None:\n",
    "            return\n",
    "\n",
    "        a_head = self.find(node_a)\n",
    "        b_head = self.find(node_b)\n",
    "\n",
    "        if(a_head != b_head):\n",
    "            a_set_size = self.size_dict[a_head]\n",
    "            b_set_size = self.size_dict[b_head]\n",
    "            if(a_set_size >= b_set_size):\n",
    "                self.father_dict[b_head] = a_head\n",
    "                self.size_dict[a_head] = a_set_size + b_set_size\n",
    "            else:\n",
    "                self.father_dict[a_head] = b_head\n",
    "                self.size_dict[b_head] = a_set_size + b_set_size\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        board = [[0] * n for _ in range(m)] \n",
    "        ufs = UnionFindSet(list(range(m*n)))\n",
    "\n",
    "        res = []\n",
    "        cur = 0 \n",
    "        for x, y in positions:\n",
    "            if board[x][y] == 1:\n",
    "                res.append(cur)\n",
    "            else:\n",
    "                board[x][y] = 1 \n",
    "                cur+=1 \n",
    "                if 0<=x+1<m and 0<=y<n and board[x+1][y]==1 and not ufs.is_same_set(x*n + y, (x+1)*n + y):\n",
    "                    ufs.union(x*n + y, (x+1)*n + y)\n",
    "                    cur -= 1\n",
    "                    \n",
    "                    \n",
    "                if 0<=x-1<m and 0<=y<n and board[x-1][y]==1 and not ufs.is_same_set(x*n + y, (x-1)*n + y):\n",
    "                    ufs.union(x*n + y, (x-1)*n + y)\n",
    "                    cur-=1\n",
    "\n",
    "                if 0<=x<m and 0<=y+1<n and board[x][y+1]==1 and not ufs.is_same_set(x*n + y, x*n + y+1):\n",
    "                    ufs.union(x*n + y, x*n + y+1)\n",
    "                    cur-=1 \n",
    "\n",
    "                if 0<=x<m and 0<=y-1<n and board[x][y-1]==1 and not ufs.is_same_set(x*n + y, x*n + y-1):\n",
    "                    ufs.union(x*n + y, x*n + y-1)\n",
    "                    cur-=1 \n",
    "                \n",
    "                res.append(cur)\n",
    "        \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "\n",
    "        root = list(range(m * n))\n",
    "        rks = [0] * (m * n)\n",
    "\n",
    "        self.cnt = 0\n",
    "\n",
    "        def find(x):\n",
    "            if root[x] != x:\n",
    "                root[x] = find(root[x])\n",
    "            return root[x]\n",
    "        \n",
    "        def connect(x, y):\n",
    "            r1, r2 = find(x), find(y)\n",
    "            if r1 != r2:\n",
    "                if rks[r1] > rks[r2]:\n",
    "                    root[r2] = r1\n",
    "                elif rks[r1] < rks[r2]:\n",
    "                    root[r1] = r2\n",
    "                else:\n",
    "                    root[r1] = r2\n",
    "                    rks[r2] += 1\n",
    "                self.cnt += 1\n",
    "        \n",
    "        res = []\n",
    "        nn = 0\n",
    "        seen = set([])\n",
    "        for x, y in positions:\n",
    "            curr_p = x * n + y\n",
    "            nn += curr_p not in seen\n",
    "            seen.add(curr_p)\n",
    "            for nx, ny in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:\n",
    "                prev_p = nx * n + ny\n",
    "                if 0 <= nx < m and 0 <= ny < n and prev_p in seen:\n",
    "                    connect(curr_p, prev_p)\n",
    "            res.append(nn - self.cnt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        dc, res, sm, POS = {}, [], 0, ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "        def find(x):\n",
    "            if dc[x]!=x: dc[x] = find(dc[x])\n",
    "            return dc[x]\n",
    "        for x,y in positions:\n",
    "            key = (x,y)\n",
    "            if key not in dc:\n",
    "                lis = set()\n",
    "                for dx, dy in POS:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < m and 0 <= ny < n and (nx,ny) in dc: lis.add(find((nx,ny)))\n",
    "                if lis:\n",
    "                    fkey = lis.pop()\n",
    "                    for nkey in lis: dc[nkey], sm = fkey, sm - 1\n",
    "                    dc[key] = fkey\n",
    "                else: dc[key], sm = key, sm + 1\n",
    "            res.append(sm)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        fa=collections.defaultdict()\n",
    "        grid=[[0 for _ in range(n)]for _ in range(m)]\n",
    "        d=[[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        def find(x):\n",
    "            if x not in fa:\n",
    "                fa[x]=x\n",
    "                return x\n",
    "            if fa[x]==x:\n",
    "                return x\n",
    "            fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(a,b):\n",
    "            if find(a)!=find(b):\n",
    "                fa[find(a)]=find(b)\n",
    "        ls=[]\n",
    "        for a,b in positions:\n",
    "            if grid[a][b]==1:\n",
    "                ls.append(ls[-1])\n",
    "                continue\n",
    "            if ls:\n",
    "                ls.append(ls[-1]+1)\n",
    "            else:\n",
    "                ls.append(1)\n",
    "            #print(ls)\n",
    "            grid[a][b]=1\n",
    "            find((a,b))\n",
    "            for d1,d2 in d:\n",
    "                aa,bb=a+d1,b+d2\n",
    "                if 0<=aa<m and 0<=bb<n:\n",
    "                    if grid[aa][bb]==1:\n",
    "                        if find((aa,bb))!=find((a,b)):\n",
    "                            union((a,b),(aa,bb))\n",
    "                            ls[-1]-=1\n",
    "        return ls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.num_island = 0\n",
    "        self.parent = {}\n",
    "\n",
    "    def add(self, x):\n",
    "        if x not in self.parent:\n",
    "            self.parent[x] = None\n",
    "            self.num_island += 1\n",
    "        \n",
    "    def find(self, x):\n",
    "        root = x\n",
    "        while self.parent[root] != None:\n",
    "            root = self.parent[root]\n",
    "        while x != root:\n",
    "            origin_par = self.parent[x]\n",
    "            self.parent[x] = root\n",
    "            x = origin_par\n",
    "        return root\n",
    "            \n",
    "    def merge(self, x, y):\n",
    "        root_x, root_y = self.find(x), self.find(y)\n",
    "        if root_x != root_y:\n",
    "            self.parent[root_x] = root_y\n",
    "            self.num_island -= 1\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        self.res = []\n",
    "        uf = UnionFind()\n",
    "        row_record = collections.defaultdict(list)\n",
    "        column_record = collections.defaultdict(list)\n",
    "        for position in positions:\n",
    "            position_tuple = tuple(position)\n",
    "            uf.add(position_tuple)\n",
    "            for item in row_record[position[0]]:\n",
    "                if abs(item[1]-position[1]) == 1:\n",
    "                    uf.merge(item, position_tuple)\n",
    "            for item in column_record[position[1]]:\n",
    "                if abs(item[0]-position[0]) == 1:\n",
    "                    uf.merge(item, position_tuple)\n",
    "\n",
    "            row_record[position[0]].append(position_tuple)\n",
    "            column_record[position[1]].append(position_tuple)\n",
    "            self.res.append(uf.num_island)\n",
    "        return self.res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        uf = UnionFind()\n",
    "        seen = set()\n",
    "        ans,count = [],0\n",
    "        for x,y in positions:\n",
    "            if (x,y) in seen:\n",
    "                ans.append(count)\n",
    "            else:\n",
    "                uf.add((x,y))\n",
    "                count += 1\n",
    "                seen.add((x,y))\n",
    "                for nx,ny in (x + 1,y),(x - 1,y),(x,y - 1),(x,y + 1):\n",
    "                    if 0 <= nx < m and 0 <= ny < n and (nx,ny) in seen:\n",
    "                        if not uf.is_connected((x,y), (nx,ny)):\n",
    "                            uf.union((x,y),(nx,ny))\n",
    "                            count -= 1\n",
    "                ans.append(count)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        记录每个节点的父节点\n",
    "        \"\"\"\n",
    "        self.father = {}\n",
    "        self.rank = defaultdict(int)\n",
    "\n",
    "    def find(self, x):\n",
    "        \"\"\"\n",
    "        查找根节点\n",
    "        路径压缩\n",
    "        \"\"\"\n",
    "        if self.father[x] != x:\n",
    "            self.father[x] = self.find(self.father[x])\n",
    "        return self.father[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        \"\"\"\n",
    "        合并两个节点\n",
    "        \"\"\"\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x != y:\n",
    "            if self.rank[x] < self.rank[y]:\n",
    "                self.father[x] = y\n",
    "            else:\n",
    "                self.father[y] = x\n",
    "                if self.rank[x] == self.rank[y]:\n",
    "                    self.rank[x] += 1\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        \"\"\"\n",
    "        判断两节点是否相连\n",
    "        \"\"\"\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def add(self, x):\n",
    "        \"\"\"\n",
    "        添加新节点\n",
    "        \"\"\"\n",
    "        if x not in self.father:\n",
    "            self.father[x] = x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        self.cnt={}\n",
    "        res=0\n",
    "        ress=[]\n",
    "        present=0\n",
    "        for r,c in positions:\n",
    "            # print(\"CNT\",self.cnt)\n",
    "            pos=r*100000+c \n",
    "            neibs=self.get_neib(m,n,pos)\n",
    "            # print(\"Neib\",r,c,neibs,pos)\n",
    "            mark=[]\n",
    "            for k,v in self.cnt.items():\n",
    "                if pos in v:\n",
    "                    mark.append(k)\n",
    "            if len(mark)!=0:\n",
    "                for index in range(1,len(mark)):\n",
    "                    res-=1\n",
    "                    mk=mark[index]\n",
    "                    self.cnt[mark[0]]|=self.cnt[mk]\n",
    "                    self.cnt.pop(mk)\n",
    "                self.cnt[mark[0]]|=set(neibs)\n",
    "                self.cnt[mark[0]].add(pos)\n",
    "                ress.append(res)\n",
    "            else:\n",
    "                res+=1\n",
    "                self.cnt[present]=set(neibs)\n",
    "                self.cnt[present].add(pos)\n",
    "                ress.append(res)\n",
    "                present+=1\n",
    "        \n",
    "        return ress \n",
    "\n",
    "    def get_neib(self,m,n,pos):\n",
    "        r=pos//100000\n",
    "        c=pos%100000\n",
    "        next_pos=[]\n",
    "        move=[[-1,0],[1,0],[0,1],[0,-1]]\n",
    "        for mm in move:\n",
    "            next_r=r+mm[0]\n",
    "            next_c=c+mm[1]\n",
    "\n",
    "            if next_r>=0 and next_r<m and next_c>=0 and next_c<n:\n",
    "                neib=next_r*100000+next_c\n",
    "                next_pos.append(neib)\n",
    "        return next_pos\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        choices = [[0, -1], [0, 1], [-1, 0], [1, 0]]\n",
    "        parent = [[(i, j) for j in range(n)] for i in range(m)]\n",
    "\n",
    "        def find(i1, j1):\n",
    "            if parent[i1][j1] != (i1, j1):\n",
    "                parent[i1][j1] = find(parent[i1][j1][0], parent[i1][j1][1])\n",
    "            return parent[i1][j1]\n",
    "        \n",
    "        def union(i1, j1, i2, j2):\n",
    "            rep1, rep2 = find(i1, j1), find(i2, j2)\n",
    "            if rep1 != rep2:\n",
    "                parent[rep1[0]][rep1[1]] = rep2\n",
    "        \n",
    "        result = [0]\n",
    "        painted_one_positions = set()\n",
    "        for pos in positions:\n",
    "            if tuple(pos) in painted_one_positions:\n",
    "                result.append(result[-1])\n",
    "                continue\n",
    "\n",
    "            painted_one_positions.add(tuple(pos))\n",
    "            valid_new_poss = []\n",
    "            for c in choices:\n",
    "                new_pos = [pos[0]+c[0], pos[1]+c[1]]\n",
    "                if 0 <= new_pos[0] < m and 0 <= new_pos[1] < n:\n",
    "                    valid_new_poss.append(new_pos)\n",
    "            \n",
    "            one_poss = []\n",
    "            for valid_new_pos in valid_new_poss:\n",
    "                if tuple(valid_new_pos) in painted_one_positions:\n",
    "                    one_poss.append(valid_new_pos)\n",
    "            \n",
    "            if not len(one_poss):\n",
    "                result.append(result[-1]+1)\n",
    "            else:\n",
    "                ones_parents = set()\n",
    "                for one_pos in one_poss:\n",
    "                    ones_parents.add(find(one_pos[0], one_pos[1]))\n",
    "                result.append(result[-1]-(len(ones_parents)-1))\n",
    "                for one_pos in one_poss:\n",
    "                    union(pos[0], pos[1], one_pos[0], one_pos[1])\n",
    "                # compress\n",
    "                # parent = [[find(parent[i][j][0], parent[i][j][1]) for j in range(n)] for i in range(m)]\n",
    "        \n",
    "        return result[1:]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Uset:\n",
    "    def __init__(self, M, N):\n",
    "        self.count = 0\n",
    "        self.parent = {}\n",
    "        self.size = {}\n",
    "        self.data = set()\n",
    "        for i in range(M):\n",
    "            for j in range(N):\n",
    "                self.parent[(i,j)] = (i, j)\n",
    "                self.size[(i, j)] = 1\n",
    "\n",
    "    def register(self, x):\n",
    "        self.data.add(x)\n",
    "        self.count += 1\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        fy = self.find(y)\n",
    "        fx = self.find(x)\n",
    "        if fy != fx:\n",
    "            self.count -= 1\n",
    "            if self.size[fx] <= self.size[fy]:\n",
    "                self.parent[fx] = fy\n",
    "                self.size[fy] += self.size[fx]\n",
    "                self.size[fx] = 0\n",
    "            else:\n",
    "                self.parent[fy] = fx\n",
    "                self.size[fx] += self.size[fy]\n",
    "                self.size[fy] = 0\n",
    "    \n",
    "    def get_count(self):\n",
    "        return self.count\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        num = 1\n",
    "        uset = Uset(m, n)\n",
    "        direc = [-1, 0, 1, 0, -1]\n",
    "        ans = []\n",
    "        for i in range(len(positions)):\n",
    "            pos = tuple(positions[i])\n",
    "            if pos in uset.data:\n",
    "                ans.append(uset.get_count())\n",
    "                continue\n",
    "            uset.register(pos)\n",
    "            for k in range(4):\n",
    "                new_pos = (pos[0] + direc[k], pos[1] + direc[k+1])\n",
    "                if new_pos in uset.data:\n",
    "                    uset.union(new_pos, pos)\n",
    "            ans.append(uset.get_count())\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Uset:\n",
    "    def __init__(self, M, N):\n",
    "        self.count = 0\n",
    "        self.parent = {}\n",
    "        self.size = {}\n",
    "        self.data = set()\n",
    "        for i in range(M):\n",
    "            for j in range(N):\n",
    "                self.parent[(i,j)] = (i, j)\n",
    "                self.size[(i, j)] = 1\n",
    "\n",
    "    def register(self, x):\n",
    "        self.data.add(x)\n",
    "        self.count += 1\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        fy = self.find(y)\n",
    "        fx = self.find(x)\n",
    "        if fy != fx:\n",
    "            self.count -= 1\n",
    "            if self.size[fx] < self.size[fy]:\n",
    "                self.parent[fx] = fy\n",
    "            elif self.size[fx] > self.size[fy]:\n",
    "                self.parent[fy] = fx\n",
    "            else:\n",
    "                self.parent[fx] = fy\n",
    "                self.size[fy] += 1\n",
    "        \n",
    "    \n",
    "    def get_count(self):\n",
    "        return self.count\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        num = 1\n",
    "        uset = Uset(m, n)\n",
    "        direc = [-1, 0, 1, 0, -1]\n",
    "        ans = []\n",
    "        for i in range(len(positions)):\n",
    "            pos = tuple(positions[i])\n",
    "            if pos in uset.data:\n",
    "                ans.append(uset.get_count())\n",
    "                continue\n",
    "            uset.register(pos)\n",
    "            for k in range(4):\n",
    "                new_pos = (pos[0] + direc[k], pos[1] + direc[k+1])\n",
    "                if new_pos in uset.data:\n",
    "                    uset.union(new_pos, pos)\n",
    "            ans.append(uset.get_count())\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        ans = 0\n",
    "        res = []\n",
    "        matrix = [[0] * n for _ in range(m)]\n",
    "\n",
    "        parent={}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                parent[(i,j)] = (i,j)\n",
    "\n",
    "        def find(p):\n",
    "            if parent[p] != p:\n",
    "                parent[p] = find(parent[p])\n",
    "            return parent[p]\n",
    "\n",
    "        def union(p,q):\n",
    "            if find(p) == find(q):\n",
    "                return False \n",
    "            else:\n",
    "                parent[find(p)] = find(q)\n",
    "                return True\n",
    "\n",
    "        for x,y in positions:\n",
    "            if matrix[x][y] == 1:\n",
    "                res.append(ans)\n",
    "                continue\n",
    "            ans+=1\n",
    "            matrix[x][y] = 1\n",
    "\n",
    "            for i,j in [(0,1), (0,-1), (-1,0), (1,0)]:\n",
    "                xx=x+i \n",
    "                yy=y+j \n",
    "                if m>xx>=0 and n>yy>=0 and matrix[xx][yy] == 1:\n",
    "                    #print(union((xx,yy), (x,y)))\n",
    "                    ans-= union((xx,yy), (x,y))\n",
    "            res.append(ans)\n",
    "\n",
    "        return res\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        added=set() # element: tuple(r,c)\n",
    "        islands=[] # element: set of tuples (r,c)\n",
    "        islands_count=[]\n",
    "        for [r,c] in positions:\n",
    "            if (r,c) not in added:\n",
    "                added.add((r,c))\n",
    "                # 查找可行的邻居位置\n",
    "                neighbors=set()\n",
    "                if r>0:\n",
    "                    neighbors.add((r-1,c))\n",
    "                if c>0:\n",
    "                    neighbors.add((r,c-1))\n",
    "                if r<m-1:\n",
    "                    neighbors.add((r+1,c))\n",
    "                if c<n-1:\n",
    "                    neighbors.add((r,c+1))\n",
    "                # 分离当前岛\n",
    "                new_islands=[] # 不可融合\n",
    "                to_merge=[] # 可融合\n",
    "                for island in islands:\n",
    "                    if len(neighbors.intersection(island))>0:\n",
    "                        to_merge.append(island)\n",
    "                    else:\n",
    "                        new_islands.append(island)\n",
    "                islands=new_islands\n",
    "                # 融合\n",
    "                new_island=set([(r,c)])\n",
    "                for island in to_merge:\n",
    "                    new_island=new_island.union(island)\n",
    "                islands.append(new_island)\n",
    "            islands_count.append(len(islands))\n",
    "        return islands_count\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "\n",
    "        parent = {}\n",
    "\n",
    "        def findRoot(x):\n",
    "            p = parent[x]\n",
    "            if p != x:\n",
    "                parent[x] = findRoot(p)\n",
    "\n",
    "            return parent[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            px, py = findRoot(x), findRoot(y)\n",
    "            if px != py:\n",
    "                parent[px] = py\n",
    "                return False\n",
    "\n",
    "            return True\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                parent[(i, j)] = (i, j)\n",
    "\n",
    "        lands = set()\n",
    "        directions = [0, 1, 0, -1]\n",
    "        count = 0\n",
    "        result = []\n",
    "        for r, c in positions:\n",
    "            if (r, c) not in lands:\n",
    "                count += 1\n",
    "                lands.add((r, c))\n",
    "                for k in range(-1, 3):\n",
    "                    nextR, nextC = r + directions[k], c + directions[k + 1]\n",
    "                    if 0 <= nextR < m and 0 <= nextC < n and (nextR, nextC) in lands:\n",
    "                        if not union((r, c), (nextR, nextC)):\n",
    "                            count -= 1\n",
    "\n",
    "            result.append(count)\n",
    "\n",
    "        # print(parent)\n",
    "        return result\n",
    "                    \n",
    "\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        parents = {}\n",
    "        offsets = [(0, 1), (1, 0), (-1, 0), (0, -1)]\n",
    "        matrix = [[0] * n for _ in range(m)]\n",
    "\n",
    "        def find(i, j):\n",
    "            if parents[(i, j)] != (i, j):\n",
    "                parents[(i, j)] = find(*parents[(i, j)])\n",
    "            return parents[(i, j)]\n",
    "        \n",
    "        def union(i, j, next_i, next_j):\n",
    "            root_1 = find(i, j)\n",
    "            root_2 = find(next_i, next_j)\n",
    "            if root_1 == root_2:\n",
    "                return False\n",
    "            parents[root_1] = root_2\n",
    "            return True\n",
    "        \n",
    "        ret_list = []\n",
    "        added = set()\n",
    "        nodes = 0\n",
    "        for i, j in positions:\n",
    "            if (i, j) in added:\n",
    "                ret_list.append(ret_list[-1])\n",
    "                continue\n",
    "            added.add((i, j))\n",
    "            nodes += 1\n",
    "            parents[(i, j)] = (i, j)\n",
    "            for offset_i, offset_j in offsets:\n",
    "                next_i = i + offset_i\n",
    "                next_j = j + offset_j\n",
    "                if (next_i, next_j) in added:\n",
    "                    nodes -= union(i, j, next_i, next_j)\n",
    "            ret_list.append(nodes)\n",
    "\n",
    "        return ret_list\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        island = [[0] * n for _ in range(m)]\n",
    "        root = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                root[i][j] = (i, j)\n",
    "        def find(x, y):\n",
    "            if root[x][y] != (x, y):\n",
    "                return find(root[x][y][0], root[x][y][1])\n",
    "            else:\n",
    "                return (x, y)\n",
    "        def union(x1, y1, x2, y2):\n",
    "            p1 = find(x1, y1)\n",
    "            p2 = find(x2, y2)\n",
    "            root[p1[0]][p1[1]] = p2\n",
    "        count = 0\n",
    "        ans = []\n",
    "        for u, v in positions:\n",
    "            if island[u][v] == 1:\n",
    "                ans.append(count)\n",
    "                continue\n",
    "            island[u][v] = 1\n",
    "            s = set([])\n",
    "            if u > 0 and island[u-1][v] == 1:\n",
    "                s.add(find(u-1, v))\n",
    "            if u+1 < m and island[u+1][v] == 1:\n",
    "                s.add(find(u+1, v))\n",
    "            if v > 0 and island[u][v-1] == 1:\n",
    "                s.add(find(u, v-1))\n",
    "            if v+1 < n and island[u][v+1] == 1:\n",
    "                s.add(find(u, v+1))\n",
    "            count = count + 1 - len(s)\n",
    "            ans.append(count)\n",
    "            for p in s:\n",
    "                root[p[0]][p[1]] = (u, v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        dict = {}\n",
    "        graph = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dict[(i, j)] = (i, j)\n",
    "\n",
    "        def find(a):\n",
    "            if dict[a] == a:\n",
    "                return a\n",
    "            p = dict[a]\n",
    "            newP = find(p)\n",
    "            dict[a] = newP\n",
    "            return newP\n",
    "\n",
    "        count = 0\n",
    "        res = []\n",
    "        for p in positions:\n",
    "            if graph[p[0]][p[1]] == 1:\n",
    "                res.append(count)\n",
    "            else:\n",
    "                graph[p[0]][p[1]] = 1\n",
    "                pl, pr, pu, pd = (-1, -1), (-1, -1), (-1, -1), (-1, -1)\n",
    "                if p[0]-1>=0 and graph[p[0]-1][p[1]] == 1:\n",
    "                    pu = find((p[0]-1, p[1]))\n",
    "                if p[0]+1<m and graph[p[0]+1][p[1]] == 1:\n",
    "                    pd = find((p[0]+1, p[1]))\n",
    "                if p[1]-1>=0 and graph[p[0]][p[1]-1] == 1:\n",
    "                    pl = find((p[0], p[1]-1))\n",
    "                if p[1]+1<n and graph[p[0]][p[1]+1] == 1:\n",
    "                    pr = find((p[0], p[1]+1))\n",
    "                nei = [pl, pr, pu, pd]\n",
    "                distinct = set()\n",
    "                for i in range(4):\n",
    "                    if nei[i] != (-1, -1):\n",
    "                        distinct.add(nei[i])\n",
    "                        dict[nei[i]] = (p[0], p[1])\n",
    "                count = count - len(distinct) + 1\n",
    "                res.append(count)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        parent = {}\n",
    "        ans = []\n",
    "        cnt = 0\n",
    "        matrix = [[0]*n for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                parent[(i,j)] = (i,j)\n",
    "\n",
    "        def find(p):\n",
    "            if parent[p] != p:\n",
    "                parent[p] = find(parent[p])\n",
    "            return parent[p]\n",
    "\n",
    "        def union(p, q):\n",
    "            if find(p) == find(q):\n",
    "                return False \n",
    "            else:\n",
    "                parent[find(p)] = find(q)\n",
    "                return True\n",
    "\n",
    "        for x,y in positions:\n",
    "            if matrix[x][y] ==1:\n",
    "                ans.append(cnt)\n",
    "                continue          ######\n",
    "            matrix[x][y] = 1\n",
    "            cnt +=1\n",
    "            for i, j in [(0,1), (0,-1), (1,0), (-1,0)]:\n",
    "                if 0<=i+x<m and 0<=j+y<n and matrix[i+x][j+y]==1:\n",
    "                    cnt -= union((x,y), (x+i, y+j))                                     ###################\n",
    "            ans.append(cnt)\n",
    "\n",
    "        return ans\n",
    "\n",
    "        #  O(nlog(mn)),  O(mn)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        parent = {}\n",
    "        self.count = 0\n",
    "        ans = []\n",
    "        water = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                parent[(i,j)]=(i,j)\n",
    "        def find(x):\n",
    "            if x!= parent[x]:\n",
    "                parent[x]=find(parent[x])\n",
    "            return parent[x]\n",
    "        def union(x,y):\n",
    "            px = find(x)\n",
    "            py = find(y)\n",
    "            if px!=py:\n",
    "                parent[px]=py\n",
    "                self.count-=1\n",
    "        for r, c in positions:\n",
    "            if (r,c) not in water:\n",
    "                water.add((r,c))\n",
    "                self.count+=1\n",
    "                for nr, nc in (r-1,c),(r+1,c),(r,c-1),(r,c+1):\n",
    "                    if 0<=nr< m and 0<=nc<n and (nr,nc) in water:\n",
    "                        union((r,c), (nr,nc))\n",
    "                ans.append(self.count)\n",
    "            else:\n",
    "                ans.append(ans[-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        grid = [[0 for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        cur_land = 0\n",
    "        land_list = []\n",
    "        for idx, (i, j) in enumerate(positions):\n",
    "            cur_land += self.op(grid, i, j, idx+1)\n",
    "            land_list.append(cur_land)\n",
    "        return land_list\n",
    "    \n",
    "    def op(self, grid, i, j, cur_id):\n",
    "        if grid[i][j] != 0:\n",
    "            return 0\n",
    "\n",
    "        cur_state = 1\n",
    "        exist_id = float('+inf')\n",
    "        if i > 0 and grid[i-1][j] != 0:\n",
    "            exist_id = min(exist_id, grid[i-1][j])\n",
    "\n",
    "        if i < len(grid)-1 and grid[i+1][j] != 0:\n",
    "            exist_id = min(exist_id, grid[i+1][j])\n",
    "        \n",
    "        if j > 0 and grid[i][j-1] != 0:\n",
    "            exist_id = min(exist_id, grid[i][j-1])\n",
    "        \n",
    "        if j < len(grid[0]) - 1 and grid[i][j+1] != 0:\n",
    "            exist_id = min(exist_id, grid[i][j+1])\n",
    "\n",
    "        if exist_id != float('+inf'):\n",
    "            cur_state -= 1\n",
    "\n",
    "        cur_id = min(exist_id, cur_id)\n",
    "        grid[i][j] = cur_id\n",
    "        if i > 0 and grid[i-1][j] != 0:\n",
    "            if self.run(grid, i-1, j, cur_id):\n",
    "                cur_state -= 1\n",
    "\n",
    "        if i < len(grid)-1 and grid[i+1][j] != 0:\n",
    "            if self.run(grid, i+1, j, cur_id):\n",
    "                cur_state -= 1\n",
    "        \n",
    "        if j > 0 and grid[i][j-1] != 0:\n",
    "            if self.run(grid, i, j-1, cur_id):\n",
    "                cur_state -= 1\n",
    "        \n",
    "        if j < len(grid[0]) - 1 and grid[i][j+1] != 0:\n",
    "            if self.run(grid, i, j+1, cur_id):\n",
    "                cur_state -= 1\n",
    "        return cur_state\n",
    "        \n",
    "    def run(self, grid, i, j, cur_id):\n",
    "        if grid[i][j] == cur_id:\n",
    "            return False\n",
    "        grid[i][j] = cur_id\n",
    "        if i > 0 and grid[i-1][j] > 0:\n",
    "            self.run(grid, i-1, j, cur_id)\n",
    "        if i < len(grid)-1 and grid[i+1][j] > 0:\n",
    "            self.run(grid, i+1, j, cur_id)\n",
    "        if j > 0 and grid[i][j-1] > 0:\n",
    "            self.run(grid, i, j-1, cur_id)\n",
    "        if j < len(grid[0]) - 1 and grid[i][j+1] > 0:\n",
    "            self.run(grid, i, j+1, cur_id)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        land={}\n",
    "        count=1\n",
    "        ans=[]\n",
    "        def dfs(i,j,tmp):\n",
    "            if not 0<=i<m or not 0<=j<n: return\n",
    "            land[tuple([i,j])]=tmp\n",
    "            if tuple([i-1,j]) in land and land[tuple([i-1,j])]!=tmp:\n",
    "                dfs(i-1,j,tmp)\n",
    "            if tuple([i+1,j]) in land and land[tuple([i+1,j])]!=tmp:\n",
    "                dfs(i+1,j,tmp)\n",
    "            if tuple([i,j-1]) in land and land[tuple([i,j-1])]!=tmp:\n",
    "                dfs(i,j-1,tmp)\n",
    "            if tuple([i,j+1]) in land and land[tuple([i,j+1])]!=tmp:\n",
    "                dfs(i,j+1,tmp)\n",
    "        for i,j in positions:\n",
    "            if tuple([i-1,j]) in land:\n",
    "                tmp=land[tuple([i-1,j])]\n",
    "                dfs(i,j,tmp)\n",
    "            elif tuple([i+1,j]) in land:\n",
    "                tmp=land[tuple([i+1,j])]\n",
    "                dfs(i,j,tmp)\n",
    "            elif tuple([i,j-1]) in land:\n",
    "                tmp=land[tuple([i,j-1])]\n",
    "                dfs(i,j,tmp)\n",
    "            elif tuple([i,j+1]) in land:\n",
    "                tmp=land[tuple([i,j+1])]\n",
    "                dfs(i,j,tmp)\n",
    "            else:\n",
    "                land[tuple([i,j])]=count\n",
    "                count+=1\n",
    "            ans.append(len(set(land.values())))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        islands = 0\n",
    "        grid = [[0] * n for _ in range(m)]\n",
    "        def is_valid(grid, i,j,m,n):\n",
    "            if i >= 0 and i < m and j >= 0 and j < n :\n",
    "                if grid[i][j] != 0:\n",
    "                    return grid[i][j]\n",
    "            return 0\n",
    "            \n",
    "        def dfs(grid,i,j,m,n, target, visited):\n",
    "            if is_valid(grid, i, j, m, n) != 0 and grid[i][j] != 0 and (i, j) not in visited:\n",
    "                grid[i][j] = target\n",
    "                visited.add((i,j))\n",
    "                dfs(grid, i-1, j, m, n, target, visited)\n",
    "                dfs(grid, i+1, j, m, n, target, visited)\n",
    "                dfs(grid, i, j-1, m, n, target, visited)\n",
    "                dfs(grid, i, j+1, m, n, target, visited)\n",
    "\n",
    "        answer = []\n",
    "\n",
    "        for i in positions:\n",
    "            connected = set()\n",
    "            mem = {}\n",
    "            if grid[i[0]][i[1]] != 0:\n",
    "                answer.append(answer[-1])\n",
    "                continue\n",
    "\n",
    "            todos = [(i[0]-1, i[1]), (i[0]+1, i[1]), (i[0], i[1]-1), (i[0], i[1]+1)]\n",
    "            for candidate in todos:\n",
    "                il = is_valid(grid, candidate[0], candidate[1], m, n)\n",
    "                if il != 0:\n",
    "                    connected.add(il)\n",
    "                    if il not in mem:\n",
    "                        mem[il] = (candidate[0], candidate[1])\n",
    "                \n",
    "\n",
    "            if not answer:\n",
    "                grid[i[0]][i[1]] = 1\n",
    "                islands = 1\n",
    "                answer = [1]\n",
    "            elif len(connected) == 0:\n",
    "                islands += 1\n",
    "                grid[i[0]][i[1]] = islands\n",
    "                answer.append(answer[-1] + 1)\n",
    "            elif len(connected) == 1:\n",
    "                grid[i[0]][i[1]] = list(connected)[0]\n",
    "                answer.append(answer[-1])\n",
    "            else:\n",
    "                target = min(connected)\n",
    "                for k, v in mem.items():\n",
    "                    if k != target:\n",
    "                        dfs(grid, v[0], v[1], m, n, target, set())\n",
    "                grid[i[0]][i[1]] = target\n",
    "                answer.append(answer[-1] - len(connected) + 1)\n",
    "\n",
    "\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        matrix = [[0] *n for _ in range(m)]\n",
    "        directions = [[1, 0],[-1, 0],[0, 1],[0, -1]]\n",
    "        ans = [1]\n",
    "        matrix[positions[0][0]][positions[0][1]] = len(positions)\n",
    "\n",
    "        def find(x, y, target):\n",
    "            if x<0 or x==m or y<0 or y==n or matrix[x][y] == 0 or matrix[x][y] ==target:\n",
    "                return\n",
    "            matrix[x][y] = target\n",
    "\n",
    "            for d in  directions:\n",
    "                find(x+d[0],y+d[1], target )\n",
    "\n",
    "        for i in range(1, len(positions)):\n",
    "            x, y, curr = positions[i][0], positions[i][1], ans[-1]\n",
    "            if matrix[x][y] == 0: \n",
    "                for d in  directions:\n",
    "                    if x+d[0]>-1 and x+d[0]<m and y+d[1]>-1 and y+d[1]<n and matrix[x+d[0]][y+d[1]]>0:\n",
    "                        if matrix[x+d[0]][y+d[1]]!=matrix[x][y]:\n",
    "                            if matrix[x][y] == 0:\n",
    "                                matrix[x][y] = matrix[x+d[0]][y+d[1]]\n",
    "                            else:\n",
    "                                curr-=1\n",
    "                                find(x+d[0],y+d[1], matrix[x][y])\n",
    "                \n",
    "                if matrix[x][y] == 0:\n",
    "                    curr+=1\n",
    "                    matrix[x][y] = i\n",
    "            ans.append(curr)\n",
    "            # print(matrix)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        grid = [[0]*n for _ in range(m)]\n",
    "        self.ans = 0\n",
    "        self.nx_color = 1\n",
    "\n",
    "        def union(x, y):\n",
    "            if grid[x][y]:\n",
    "                return self.ans\n",
    "            colors = [grid[i][j] for i, j in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)] if 0 <= i < m and 0 <= j < n and grid[i][j] != 0]\n",
    "            if not colors:\n",
    "                grid[x][y] = self.nx_color\n",
    "                self.nx_color += 1\n",
    "            else:\n",
    "                grid[x][y] = colors[0]\n",
    "                self.ans -= len(set(colors))\n",
    "                color(x, y, colors[0])\n",
    "            self.ans += 1\n",
    "            return self.ans\n",
    "\n",
    "        def color(x, y, c):\n",
    "            for i, j in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:\n",
    "                if 0 <= i < m and 0 <= j < n and grid[i][j] != c and grid[i][j]:\n",
    "                    grid[i][j] = c\n",
    "                    color(i, j, c)\n",
    "\n",
    "        res = [union(*pos) for pos in positions]\n",
    "        return res\n",
    "\n",
    "\"\"\"\n",
    "1 1 0\n",
    "0 0 2\n",
    "0 0 0\n",
    "\"\"\"\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import numpy as np\n",
    "class Solution(object):\n",
    "\tdef numIslands2(self, m, n, positions):\n",
    "\t\t\"\"\"\n",
    "\t\t:type m: int\n",
    "\t\t:type n: int\n",
    "\t\t:type positions: List[List[int]]\n",
    "\t\t:rtype: List[int]\n",
    "\t\t\"\"\"\n",
    "\t\tgrid = np.zeros([m,n], dtype=np.int)\n",
    "\t\tdirections = [(1,0),(-1,0),(0,-1),(0,1)]\n",
    "\t\t\n",
    "\t\tres = []\n",
    "\t\tindex = 1\n",
    "\t\tisland = collections.defaultdict(set)\n",
    "\t\tfor x,y in positions:\n",
    "\t\t\tif grid[x][y]:\n",
    "\t\t\t\tres.append(len(island))\n",
    "\t\t\t\tcontinue\n",
    "\t\t\t\n",
    "\t\t\taround = []\n",
    "\t\t\tfor dx, dy in directions:\n",
    "\t\t\t\tif 0<=x+dx<m and 0<=y+dy<n:\n",
    "\t\t\t\t\tif grid[x+dx][y+dy] and grid[x+dx][y+dy] not in around:\n",
    "\t\t\t\t\t\taround.append(grid[x+dx][y+dy])\n",
    "\t\t\t\n",
    "\t\t\tif len(around) == 0:\n",
    "\t\t\t\tgrid[x][y] = index\n",
    "\t\t\t\tisland[index].add((x,y))\n",
    "\t\t\t\tindex += 1\n",
    "\t\t\telse:\n",
    "\t\t\t\tmod_index = around[0]\n",
    "\t\t\t\tgrid[x][y] = mod_index\n",
    "\t\t\t\tisland[mod_index].add((x,y))\n",
    "\t\t\t\tfor ori_index in around[1:]:\n",
    "\t\t\t\t\tfor i,j in island[ori_index]:\n",
    "\t\t\t\t\t\tgrid[i][j] = mod_index\n",
    "\t\t\t\t\t\tisland[mod_index].add((i,j))\n",
    "\t\t\t\t\tdel island[ori_index]\n",
    "\t\t\t\n",
    "\t\t\tres.append(len(island))\n",
    "\t\treturn res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        def ajacent(x,y):\n",
    "            ret = []\n",
    "            for offset in [-1,1]:\n",
    "                x_new = x+offset\n",
    "                if x_new < 0 or x_new >= row or array[x_new,y] == 0:\n",
    "                    pass\n",
    "                else:\n",
    "                    ret.append((x_new,y))\n",
    "                y_new = y+offset\n",
    "                if y_new < 0 or y_new >= col or array[x,y_new] == 0:\n",
    "                    pass\n",
    "                else:\n",
    "                    ret.append((x,y_new))\n",
    "            return ret\n",
    "        def find(a):\n",
    "            r_a = a\n",
    "            while father[r_a] != r_a:\n",
    "                r_a = father[r_a]\n",
    "\n",
    "            while father[a] != a:\n",
    "                temp = father[a]\n",
    "                father[temp] = r_a\n",
    "                a = temp\n",
    "            return r_a\n",
    "        def uf(a,b):\n",
    "            root_a = find(a)\n",
    "            root_b = find(b)\n",
    "            if root_a != root_b:\n",
    "                father[root_b] = a\n",
    "                self.count -= 1\n",
    "\n",
    "        def add(x,y):\n",
    "            if array[x,y] == 0:\n",
    "                array[x,y] = 1\n",
    "                self.count += 1\n",
    "                father[(x,y)] = (x,y)\n",
    "                ajacent_land = ajacent(x,y)\n",
    "                for a in ajacent_land:\n",
    "                    uf((x,y), a)\n",
    "            self.res.append(self.count)\n",
    "\n",
    "        array = np.zeros((m,n))\n",
    "        row,col = array.shape\n",
    "        father = {}\n",
    "        self.count = 0\n",
    "        self.res = []\n",
    "        for x,y in positions:\n",
    "            add(x,y)\n",
    "            #print(father)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        answer_list = []\n",
    "        now_count = 0\n",
    "        grid = [[(0, 0) for i in range(n+2)] for i in range(m+2)]\n",
    "        for i in range(len(positions)):\n",
    "            positions[i][0] += 1\n",
    "            positions[i][1] += 1\n",
    "        now_island_index = 1\n",
    "        for i in positions:\n",
    "            if grid[i[0]][i[1]] != (0, 0):\n",
    "                answer_list.append(now_count)\n",
    "                continue\n",
    "            flag_no_around = True\n",
    "            for around_i in [(i[0]-1, i[1]),(i[0]+1, i[1]), (i[0], i[1]-1), (i[0], i[1]+1)]:\n",
    "                if grid[around_i[0]][around_i[1]] != (0, 0):\n",
    "                    flag_no_around = False\n",
    "                    if grid[i[0]][i[1]] == (0, 0):\n",
    "                        while around_i != grid[around_i[0]][around_i[1]]:\n",
    "                            around_i = grid[around_i[0]][around_i[1]]\n",
    "                        grid[i[0]][i[1]] = around_i\n",
    "                    else:\n",
    "                        while around_i != grid[around_i[0]][around_i[1]]:\n",
    "                            around_i = grid[around_i[0]][around_i[1]]\n",
    "                        if grid[i[0]][i[1]] == grid[around_i[0]][around_i[1]]:\n",
    "                            continue\n",
    "                        grid[around_i[0]][around_i[1]] = grid[i[0]][i[1]]\n",
    "                        now_count -= 1\n",
    "            if flag_no_around:\n",
    "                grid[i[0]][i[1]] = i\n",
    "                now_count += 1\n",
    "            answer_list.append(now_count)\n",
    "        return answer_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        answer_list = []\n",
    "        now_count = 0\n",
    "        grid = [[0 for i in range(n+2)] for i in range(m+2)]\n",
    "        for i in range(len(positions)):\n",
    "            positions[i][0] += 1\n",
    "            positions[i][1] += 1\n",
    "        print(positions)\n",
    "        print(grid)\n",
    "        now_island_index = 1\n",
    "        for i in positions:\n",
    "            if grid[i[0]][i[1]] != 0:\n",
    "                print('what?')\n",
    "                answer_list.append(now_count)\n",
    "                continue\n",
    "            flag_no_round = True\n",
    "            for j in [(i[0]-1, i[1]), (i[0]+1, i[1]), (i[0], i[1]-1), (i[0], i[1]+1)]:\n",
    "                if grid[j[0]][j[1]] != 0:\n",
    "                    flag_no_round = False\n",
    "                    if grid[i[0]][i[1]] == 0:\n",
    "                        grid[i[0]][i[1]] = grid[j[0]][j[1]]\n",
    "                    else:\n",
    "                        if grid[i[0]][i[1]] == grid[j[0]][j[1]]:\n",
    "                            continue\n",
    "                        else:\n",
    "                            tmp_index = grid[j[0]][j[1]]\n",
    "                            for tmp_i in range(m+2):\n",
    "                                for tmp_j in range(n+2):\n",
    "                                    if grid[tmp_i][tmp_j] == tmp_index:\n",
    "                                        grid[tmp_i][tmp_j] = grid[i[0]][i[1]]\n",
    "                            now_count -= 1\n",
    "            if flag_no_round:\n",
    "                grid[i[0]][i[1]] = now_island_index\n",
    "                now_count += 1\n",
    "                now_island_index += 1\n",
    "            answer_list.append(now_count)\n",
    "        return answer_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        color_positions_dict = {}\n",
    "        answer_list = []\n",
    "        now_count = 0\n",
    "        grid = [[0 for i in range(n+2)] for i in range(m+2)]\n",
    "        grid = [[0 for i in range(n+2)] for i in range(m+2)]\n",
    "        grid = [[0 for i in range(n+2)] for i in range(m+2)]\n",
    "        for i in range(len(positions)):\n",
    "            positions[i][0] += 1\n",
    "            positions[i][1] += 1\n",
    "        now_island_index = 1\n",
    "        for i in positions:\n",
    "            if grid[i[0]][i[1]] != 0:\n",
    "                answer_list.append(now_count)\n",
    "                continue\n",
    "            flag_no_round = True\n",
    "            for j in [(i[0]-1, i[1]), (i[0]+1, i[1]), (i[0], i[1]-1), (i[0], i[1]+1)]:\n",
    "                if grid[j[0]][j[1]] != 0:\n",
    "                    flag_no_round = False\n",
    "                    if grid[i[0]][i[1]] == 0:\n",
    "                        grid[i[0]][i[1]] = grid[j[0]][j[1]]\n",
    "                        color_positions_dict[grid[i[0]][i[1]]].append(i)\n",
    "                    else:\n",
    "                        if grid[i[0]][i[1]] == grid[j[0]][j[1]]:\n",
    "                            continue\n",
    "                        else:\n",
    "                            tmp_index = grid[j[0]][j[1]]\n",
    "                            for tmp_item in color_positions_dict[tmp_index]:\n",
    "                                grid[tmp_item[0]][tmp_item[1]] = grid[i[0]][i[1]]\n",
    "                            color_positions_dict[grid[i[0]][i[1]]] += color_positions_dict.pop(tmp_index)\n",
    "                            now_count -= 1\n",
    "            if flag_no_round:\n",
    "                grid[i[0]][i[1]] = now_island_index\n",
    "                color_positions_dict[now_island_index] = [i]\n",
    "                now_count += 1\n",
    "                now_island_index += 1\n",
    "            answer_list.append(now_count)\n",
    "        return answer_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class listnode:\n",
    "    def __init__(self):\n",
    "        self.next = None\n",
    "        self.island_index = None\n",
    "    \n",
    "class Solution:\n",
    "    def get_four_positions(self, p, m, n):\n",
    "        x = p[0]\n",
    "        y = p[1]\n",
    "        x_arr = [x-1, x+1]\n",
    "        y_arr = [y-1, y+1]\n",
    "        if x == 0:\n",
    "            x_arr[0] = np.nan\n",
    "        if x == m-1:\n",
    "            x_arr[1] = np.nan\n",
    "        if y == 0:\n",
    "            y_arr[0] = np.nan\n",
    "        if y == n-1:\n",
    "            y_arr[1] = np.nan\n",
    "        return ((not np.isnan(x_arr[0]), (x_arr[0], y)), (not np.isnan(x_arr[1]), (x_arr[1], y)), (not np.isnan(y_arr[0]), (x, y_arr[0])), (not np.isnan(y_arr[1]), (x, y_arr[1])))\n",
    "\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        answer = []\n",
    "        p_island_dict = {}\n",
    "        all_record_set = set()\n",
    "        now_island_index = 1\n",
    "        for p_i in positions:\n",
    "            p_i = tuple(p_i)\n",
    "            if p_i in p_island_dict:\n",
    "                answer.append(len(all_record_set))\n",
    "                continue\n",
    "            p_around = self.get_four_positions(p_i, m, n)\n",
    "            flag_no_around = True\n",
    "            for p_around_i in p_around:\n",
    "                if not p_around_i[0]:\n",
    "                    continue\n",
    "                else:\n",
    "                    if p_around_i[1] in p_island_dict:\n",
    "                        flag_no_around = False\n",
    "                        if p_i not in p_island_dict:\n",
    "                            p_island_dict[p_i] = p_island_dict[p_around_i[1]]\n",
    "                        else:\n",
    "                            tmp_p_i = p_island_dict[p_i]\n",
    "                            while tmp_p_i.next != None:\n",
    "                                tmp_p_i = tmp_p_i.next\n",
    "                            tmp_p_around_i = p_island_dict[p_around_i[1]]\n",
    "                            while tmp_p_around_i.next != None:\n",
    "                                tmp_p_around_i = tmp_p_around_i.next\n",
    "                            if tmp_p_i.island_index == tmp_p_around_i.island_index:\n",
    "                                continue\n",
    "                            else:\n",
    "                                all_record_set.remove(tmp_p_around_i.island_index)\n",
    "                                tmp_p_around_i.next = tmp_p_i\n",
    "                                # tmp_node = listnode()\n",
    "                                # tmp_node.island_index = tmp_p_i.island_index\n",
    "                                # tmp_p_i.next = tmp_node\n",
    "                                # tmp_p_around_i.next = tmp_node\n",
    "            if flag_no_around:\n",
    "                tmp_node = listnode()\n",
    "                tmp_node.island_index = now_island_index\n",
    "                p_island_dict[p_i] = tmp_node\n",
    "                all_record_set.add(now_island_index)\n",
    "                now_island_index += 1\n",
    "            answer.append(len(all_record_set))\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import numpy as np\n",
    "class listnode:\n",
    "    def __init__(self):\n",
    "        self.next = None\n",
    "        self.island_index = None\n",
    "    \n",
    "class Solution:\n",
    "    def get_four_positions(self, p, m, n):\n",
    "        x = p[0]\n",
    "        y = p[1]\n",
    "        x_arr = [x-1, x+1]\n",
    "        y_arr = [y-1, y+1]\n",
    "        if x == 0:\n",
    "            x_arr[0] = np.nan\n",
    "        if x == m-1:\n",
    "            x_arr[1] = np.nan\n",
    "        if y == 0:\n",
    "            y_arr[0] = np.nan\n",
    "        if y == n-1:\n",
    "            y_arr[1] = np.nan\n",
    "        return ((not np.isnan(x_arr[0]), (x_arr[0], y)), (not np.isnan(x_arr[1]), (x_arr[1], y)), (not np.isnan(y_arr[0]), (x, y_arr[0])), (not np.isnan(y_arr[1]), (x, y_arr[1])))\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        max_times = 0\n",
    "        answer = []\n",
    "        p_island_dict = {}\n",
    "        all_record_set = set()\n",
    "        now_island_index = 1\n",
    "        for p_i in positions:\n",
    "            p_i = tuple(p_i)\n",
    "            if p_i in p_island_dict:\n",
    "                answer.append(len(all_record_set))\n",
    "                continue\n",
    "            p_around = self.get_four_positions(p_i, m, n)\n",
    "            flag_no_around = True\n",
    "            for p_around_i in p_around:\n",
    "                if not p_around_i[0]:\n",
    "                    continue\n",
    "                else:\n",
    "                    if p_around_i[1] in p_island_dict:\n",
    "                        flag_no_around = False\n",
    "                        if p_i not in p_island_dict:\n",
    "                            if p_island_dict[p_around_i[1]].next == None:\n",
    "                                p_island_dict[p_i] = p_island_dict[p_around_i[1]]\n",
    "                            else:\n",
    "                                tmp = p_island_dict[p_around_i[1]]\n",
    "                                while tmp.next != None:\n",
    "                                    tmp = tmp.next\n",
    "                                p_island_dict[p_i] = p_island_dict[p_around_i[1]]\n",
    "                                p_island_dict[p_i].next = tmp\n",
    "                        else:\n",
    "                            tmp_p_i = p_island_dict[p_i]\n",
    "                            tmp_times = 0\n",
    "                            while tmp_p_i.next != None:\n",
    "                                tmp_times += 1\n",
    "                                tmp_p_i = tmp_p_i.next\n",
    "                            tmp_p_around_i = p_island_dict[p_around_i[1]]\n",
    "                            while tmp_p_around_i.next != None:\n",
    "                                tmp_times += 1\n",
    "                                tmp_p_around_i = tmp_p_around_i.next\n",
    "                            max_times = tmp_times if tmp_times > max_times else max_times\n",
    "                            if tmp_p_i.island_index == tmp_p_around_i.island_index:\n",
    "                                continue\n",
    "                            else:\n",
    "                                all_record_set.remove(tmp_p_around_i.island_index)\n",
    "                                tmp_p_around_i.next = tmp_p_i\n",
    "                                # tmp_node = listnode()\n",
    "                                # tmp_node.island_index = tmp_p_i.island_index\n",
    "                                # tmp_p_i.next = tmp_node\n",
    "                                # tmp_p_around_i.next = tmp_node\n",
    "            if flag_no_around:\n",
    "                tmp_node = listnode()\n",
    "                tmp_node.island_index = now_island_index\n",
    "                p_island_dict[p_i] = tmp_node\n",
    "                all_record_set.add(now_island_index)\n",
    "                now_island_index += 1\n",
    "            answer.append(len(all_record_set))\n",
    "        # if m == 100:\n",
    "        #     print(max_times)\n",
    "        #     return\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import numpy as np\n",
    "class listnode:\n",
    "    def __init__(self):\n",
    "        self.next = None\n",
    "        self.island_index = None\n",
    "    \n",
    "class Solution:\n",
    "    def get_four_positions(self, p, m, n):\n",
    "        x = p[0]\n",
    "        y = p[1]\n",
    "        x_arr = [x-1, x+1]\n",
    "        y_arr = [y-1, y+1]\n",
    "        if x == 0:\n",
    "            x_arr[0] = np.nan\n",
    "        if x == m-1:\n",
    "            x_arr[1] = np.nan\n",
    "        if y == 0:\n",
    "            y_arr[0] = np.nan\n",
    "        if y == n-1:\n",
    "            y_arr[1] = np.nan\n",
    "        return ((not np.isnan(x_arr[0]), (x_arr[0], y)), (not np.isnan(x_arr[1]), (x_arr[1], y)), (not np.isnan(y_arr[0]), (x, y_arr[0])), (not np.isnan(y_arr[1]), (x, y_arr[1])))\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        max_times = 0\n",
    "        answer = []\n",
    "        p_island_dict = {}\n",
    "        all_record_set = set()\n",
    "        now_island_index = 1\n",
    "        for p_i in positions:\n",
    "            p_i = tuple(p_i)\n",
    "            if p_i in p_island_dict:\n",
    "                answer.append(len(all_record_set))\n",
    "                continue\n",
    "            p_around = self.get_four_positions(p_i, m, n)\n",
    "            flag_no_around = True\n",
    "            for p_around_i in p_around:\n",
    "                if not p_around_i[0]:\n",
    "                    continue\n",
    "                else:\n",
    "                    if p_around_i[1] in p_island_dict:\n",
    "                        flag_no_around = False\n",
    "                        if p_i not in p_island_dict:\n",
    "                            p_island_dict[p_i] = p_island_dict[p_around_i[1]]\n",
    "                        else:\n",
    "                            tmp_p_i = p_island_dict[p_i]\n",
    "                            tmp_times = 0\n",
    "                            while tmp_p_i.next != None:\n",
    "                                tmp_times += 1\n",
    "                                tmp_p_i = tmp_p_i.next\n",
    "                            tmp_p_around_i = p_island_dict[p_around_i[1]]\n",
    "                            while tmp_p_around_i.next != None:\n",
    "                                tmp_times += 1\n",
    "                                tmp_p_around_i = tmp_p_around_i.next\n",
    "                            max_times = tmp_times if tmp_times > max_times else max_times\n",
    "                            if tmp_p_i.island_index == tmp_p_around_i.island_index:\n",
    "                                continue\n",
    "                            else:\n",
    "                                all_record_set.remove(tmp_p_around_i.island_index)\n",
    "                                tmp_p_around_i.next = tmp_p_i\n",
    "                                # tmp_node = listnode()\n",
    "                                # tmp_node.island_index = tmp_p_i.island_index\n",
    "                                # tmp_p_i.next = tmp_node\n",
    "                                # tmp_p_around_i.next = tmp_node\n",
    "            if flag_no_around:\n",
    "                tmp_node = listnode()\n",
    "                tmp_node.island_index = now_island_index\n",
    "                p_island_dict[p_i] = tmp_node\n",
    "                all_record_set.add(now_island_index)\n",
    "                now_island_index += 1\n",
    "            answer.append(len(all_record_set))\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class listnode:\n",
    "    def __init__(self):\n",
    "        self.next = None\n",
    "        self.island_index = None\n",
    "    \n",
    "class Solution:\n",
    "    def get_four_positions(self, p, m, n):\n",
    "        x = p[0]\n",
    "        y = p[1]\n",
    "        x_arr = [x-1, x+1]\n",
    "        y_arr = [y-1, y+1]\n",
    "        if x == 0:\n",
    "            x_arr[0] = np.nan\n",
    "        if x == m-1:\n",
    "            x_arr[1] = np.nan\n",
    "        if y == 0:\n",
    "            y_arr[0] = np.nan\n",
    "        if y == n-1:\n",
    "            y_arr[1] = np.nan\n",
    "        return ((not np.isnan(x_arr[0]), (x_arr[0], y)), (not np.isnan(x_arr[1]), (x_arr[1], y)), (not np.isnan(y_arr[0]), (x, y_arr[0])), (not np.isnan(y_arr[1]), (x, y_arr[1])))\n",
    "\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        answer = []\n",
    "        p_island_dict = {}\n",
    "        all_record_set = set()\n",
    "        now_island_index = 1\n",
    "        for p_i in positions:\n",
    "            p_i = tuple(p_i)\n",
    "            if p_i in p_island_dict:\n",
    "                answer.append(len(all_record_set))\n",
    "                continue\n",
    "            p_around = self.get_four_positions(p_i, m, n)\n",
    "            flag_no_around = True\n",
    "            for p_around_i in p_around:\n",
    "                if not p_around_i[0]:\n",
    "                    continue\n",
    "                else:\n",
    "                    if p_around_i[1] in p_island_dict:\n",
    "                        flag_no_around = False\n",
    "                        if p_i not in p_island_dict:\n",
    "                            p_island_dict[p_i] = p_island_dict[p_around_i[1]]\n",
    "                        else:\n",
    "                            tmp_p_i = p_island_dict[p_i]\n",
    "                            while tmp_p_i.next != None:\n",
    "                                tmp_p_i = tmp_p_i.next\n",
    "                            tmp_p_around_i = p_island_dict[p_around_i[1]]\n",
    "                            while tmp_p_around_i.next != None:\n",
    "                                tmp_p_around_i = tmp_p_around_i.next\n",
    "                            if tmp_p_i.island_index == tmp_p_around_i.island_index:\n",
    "                                continue\n",
    "                            else:\n",
    "                                all_record_set.remove(tmp_p_around_i.island_index)\n",
    "                                tmp_node = listnode()\n",
    "                                tmp_node.island_index = tmp_p_i.island_index\n",
    "                                tmp_p_i.next = tmp_node\n",
    "                                tmp_p_around_i.next = tmp_node\n",
    "            if flag_no_around:\n",
    "                tmp_node = listnode()\n",
    "                tmp_node.island_index = now_island_index\n",
    "                p_island_dict[p_i] = tmp_node\n",
    "                all_record_set.add(now_island_index)\n",
    "                now_island_index += 1\n",
    "            answer.append(len(all_record_set))\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class listnode:\n",
    "    def __init__(self):\n",
    "        self.next = None\n",
    "        self.island_index = None\n",
    "    \n",
    "class Solution:\n",
    "    def get_four_positions(self, p, m, n):\n",
    "        x = p[0]\n",
    "        y = p[1]\n",
    "        x_arr = [x-1, x+1]\n",
    "        y_arr = [y-1, y+1]\n",
    "        if x == 0:\n",
    "            x_arr[0] = np.nan\n",
    "        if x == m-1:\n",
    "            x_arr[1] = np.nan\n",
    "        if y == 0:\n",
    "            y_arr[0] = np.nan\n",
    "        if y == n-1:\n",
    "            y_arr[1] = np.nan\n",
    "        return ((not np.isnan(x_arr[0]), (x_arr[0], y)), (not np.isnan(x_arr[1]), (x_arr[1], y)), (not np.isnan(y_arr[0]), (x, y_arr[0])), (not np.isnan(y_arr[1]), (x, y_arr[1])))\n",
    "\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        answer = []\n",
    "        p_island_dict = {}\n",
    "        all_record_set = set()\n",
    "        now_island_index = 1\n",
    "        for p_i in positions:\n",
    "            p_i = tuple(p_i)\n",
    "            if p_i in p_island_dict:\n",
    "                answer.append(len(all_record_set))\n",
    "                continue\n",
    "            p_around = self.get_four_positions(p_i, m, n)\n",
    "            flag_no_around = True\n",
    "            for p_around_i in p_around:\n",
    "                if not p_around_i[0]:\n",
    "                    continue\n",
    "                else:\n",
    "                    if p_around_i[1] in p_island_dict:\n",
    "                        flag_no_around = False\n",
    "                        if p_i not in p_island_dict:\n",
    "                            p_island_dict[p_i] = p_island_dict[p_around_i[1]]\n",
    "                        else:\n",
    "                            tmp_p_i = p_island_dict[p_i]\n",
    "                            while tmp_p_i.next != None:\n",
    "                                tmp_p_i = tmp_p_i.next\n",
    "                            tmp_p_around_i = p_island_dict[p_around_i[1]]\n",
    "                            while tmp_p_around_i.next != None:\n",
    "                                tmp_p_around_i = tmp_p_around_i.next\n",
    "                            if tmp_p_i.island_index == tmp_p_around_i.island_index:\n",
    "                                continue\n",
    "                            else:\n",
    "                                all_record_set.remove(tmp_p_around_i.island_index)\n",
    "                                tmp_node = listnode()\n",
    "                                tmp_node.island_index = tmp_p_i.island_index\n",
    "                                tmp_p_i.next = tmp_node\n",
    "                                tmp_p_around_i.next = tmp_node\n",
    "            if flag_no_around:\n",
    "                tmp_node = listnode()\n",
    "                tmp_node.island_index = now_island_index\n",
    "                p_island_dict[p_i] = tmp_node\n",
    "                all_record_set.add(now_island_index)\n",
    "                now_island_index += 1\n",
    "            answer.append(len(all_record_set))\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def get_four_positions(self, p, m, n):\n",
    "        x = p[0]\n",
    "        y = p[1]\n",
    "        x_arr = [x-1, x+1]\n",
    "        y_arr = [y-1, y+1]\n",
    "        if x == 0:\n",
    "            x_arr[0] = np.nan\n",
    "        if x == m-1:\n",
    "            x_arr[1] = np.nan\n",
    "        if y == 0:\n",
    "            y_arr[0] = np.nan\n",
    "        if y == n-1:\n",
    "            y_arr[1] = np.nan\n",
    "        return ((not np.isnan(x_arr[0]), (x_arr[0], y)), (not np.isnan(x_arr[1]), (x_arr[1], y)), (not np.isnan(y_arr[0]), (x, y_arr[0])), (not np.isnan(y_arr[1]), (x, y_arr[1])))\n",
    "\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        answer = []\n",
    "        set_list = []\n",
    "        all_set = set()\n",
    "        for p_i in positions:\n",
    "            p_i = tuple(p_i)\n",
    "            if p_i in all_set:\n",
    "                answer.append(answer[-1])\n",
    "                continue\n",
    "            p_around = self.get_four_positions(p_i, m, n)\n",
    "            flag_no_around = True\n",
    "            first_added_cat = None\n",
    "            for p_around_i in p_around:\n",
    "                if not p_around_i[0]:\n",
    "                    continue\n",
    "                else:\n",
    "                    if p_around_i[1] in all_set:\n",
    "                        flag_no_around = False\n",
    "                        if p_i not in all_set:\n",
    "                            for set_index in range(len(set_list)):\n",
    "                                if p_around_i[1] in set_list[set_index]:\n",
    "                                    set_list[set_index].add(p_i)\n",
    "                                    all_set.add(p_i)\n",
    "                                    first_added_cat = set_index\n",
    "                                    break\n",
    "                        else:\n",
    "                            for set_index in range(len(set_list)):\n",
    "                                if p_around_i[1] in set_list[set_index]:\n",
    "                                    if p_i in set_list[set_index]:\n",
    "                                        continue\n",
    "                                    else:\n",
    "                                        for set_index_2 in range(len(set_list)):\n",
    "                                            if p_i in set_list[set_index_2]:\n",
    "                                                set_list[set_index] = set_list[set_index].union(set_list[set_index_2])\n",
    "                                                set_list[set_index_2] = set()\n",
    "                                                break\n",
    "                                    break\n",
    "            if flag_no_around:\n",
    "                set_list.append(set())\n",
    "                set_list[-1].add(p_i)\n",
    "                all_set.add(p_i)\n",
    "            while set() in set_list:\n",
    "                set_list.remove(set())\n",
    "            answer.append(len(set_list))\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        visited = [[0 for i in range(n)] for j in range(m)]\n",
    "        directions = [(0,1), (1,0), (0,-1), (-1,0)]\n",
    "        result = 0\n",
    "        def BFS(x, y, result, visited):\n",
    "            stack = deque()\n",
    "            stack.append((x,y))\n",
    "            while(len(stack)):\n",
    "                i, j = stack.pop()\n",
    "                visited[i][j] = result\n",
    "                for dir in directions:\n",
    "                    dir_x, dir_y = dir\n",
    "                    if 0 <= i+dir_x <= m-1 and 0 <= j+dir_y <= n-1:\n",
    "                        if  visited[i+dir_x][j+dir_y] == 0 and grid[i+dir_x][j+dir_y] == \"1\":\n",
    "                            stack.append((i+dir_x, j+dir_y))\n",
    "                            visited[i+dir_x][j+dir_y] = result\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if visited[i][j] == 0 and grid[i][j] == \"1\":\n",
    "                    result += 1\n",
    "                    BFS(i,j, result, visited)\n",
    "\n",
    "        return result\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: 'List[List[str]]') -> 'int':\n",
    "        \n",
    "        d=0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j]=='1':\n",
    "                    a=[]\n",
    "                    a.append([i,j])\n",
    "                    grid[i][j]='0'\n",
    "                    d+=1\n",
    "                    while True:\n",
    "                        c=[]\n",
    "                        for k in a:\n",
    "                            for m,n in [[-1,0],[1,0],[0,-1],[0,1]]:\n",
    "                                if k[0]+m>-1 and k[1]+n>-1:\n",
    "                                    try:\n",
    "                                        if grid[k[0]+m][k[1]+n]=='1':\n",
    "                                            grid[k[0]+m][k[1]+n]='0'\n",
    "                                            c.append([k[0]+m,k[1]+n])\n",
    "                                    except IndexError:\n",
    "                                        pass\n",
    "                        if len(c)==0:\n",
    "                            break\n",
    "                        a=c\n",
    "                        \n",
    "        return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]\n",
    "\n",
    "    def numIslands(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[str]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not grid:\n",
    "            return 0\n",
    "        count = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[i])):\n",
    "                if grid[i][j] != \"0\":\n",
    "                    count += 1\n",
    "                    self.dfs(grid, i, j)\n",
    "        return count\n",
    "\n",
    "    def dfs(self, grid, i, j):\n",
    "        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[i]) or grid[i][j] == \"0\":\n",
    "            return\n",
    "        grid[i][j] = \"0\"\n",
    "        for item in self.directions:\n",
    "            self.dfs(grid, i + item[0], j + item[1])\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[str]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def seek(i, j):\n",
    "            if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] == '1':\n",
    "                grid[i][j] = '0'\n",
    "                list(map(seek, [i+1, i-1, i, i], [j, j, j+1, j-1]))\n",
    "                return 1\n",
    "            return 0\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                ans += seek(i, j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[str]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(grid) is 0:\n",
    "            return 0\n",
    "        l, h = len(grid[0]), len(grid)\n",
    "        visited = [[False for _ in range(l)] for _ in range(h)]\n",
    "        direction = [[-1, 0], [1, 0], [0, 1], [0, -1]]\n",
    "        self.icount = 0\n",
    "        for i in range(h):\n",
    "            for j in range(l):\n",
    "                if visited[i][j] == False and grid[i][j] == \"1\":\n",
    "                    queue = [[i, j]]\n",
    "\n",
    "                    visited[i][j] = True\n",
    "                    while len(queue):\n",
    "                        node = queue.pop()\n",
    "                        i1 = node[0]\n",
    "                        j1 = node[1]\n",
    "                    \n",
    "                        for d in direction:\n",
    "                            if i1 + d[0] >= 0 and i1 + d[0] < h and j1 + d[1] >= 0 and j1 + d[1] < l:\n",
    "                                if grid[i1 + d[0]][j1 + d[1]] is \"1\" and visited[i1 + d[0]][j1 + d[1]] is False:\n",
    "                                    visited[i1 + d[0]][j1 + d[1]] = True\n",
    "                                    queue.insert(0, [i1 + d[0], j1 + d[1]])\n",
    "                    self.icount += 1\n",
    "\n",
    "        return self.icount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[str]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def islands(i,j):\n",
    "            if 0<=i<len(grid) and 0<=j<len(grid[0]) and grid[i][j]==\"1\":\n",
    "                grid[i][j] = \"0\"\n",
    "                list(map(islands,(i-1,i+1,i,i),(j,j,j+1,j-1)))\n",
    "                return 1\n",
    "            return 0\n",
    "        return sum( [islands(i,j) for i in range(len(grid)) for j in range(len(grid[i]))])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Unionfind(object):\n",
    "    def __init__(self, grid):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        self.count = 0\n",
    "        self.parent = [-1] * (m*n)\n",
    "        self.rank = [0] * (m*n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '1':\n",
    "                    self.parent[i*n + j] = i*n + j\n",
    "                    self.count += 1\n",
    "    def find(self, i):\n",
    "        if self.parent[i] != i:\n",
    "            self.parent[i] = self.find(self.parent[i])\n",
    "        return self.parent[i]\n",
    "    def union(self, x, y):\n",
    "        rootx = self.find(x)\n",
    "        rooty = self.find(y)\n",
    "        if rootx != rooty:\n",
    "            if self.rank[rootx] > self.rank[rooty]:\n",
    "                self.parent[rooty] = rootx\n",
    "            elif self.rank[rootx] < self.rank[rooty]:\n",
    "                self.parent[rootx] = rooty\n",
    "            else:\n",
    "                self.parent[rooty] = rootx\n",
    "                self.rank[rootx] += 1\n",
    "            self.count -= 1\n",
    "class Solution:\n",
    "    def numIslands(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[str]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not grid or not grid[0]:\n",
    "            return 0\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        uf = Unionfind(grid)\n",
    "        directions = [(0,1),(1,0),(0,-1),(-1,0)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '0':\n",
    "                    continue\n",
    "                for d in directions:\n",
    "                    ni, nj = i + d[0], j + d[1]\n",
    "                    if ni >= 0 and nj >=0 and ni < m and nj < n and grid[ni][nj] == '1':\n",
    "                        uf.union(i*n+j, ni*n+nj)\n",
    "        return uf.count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[str]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        mark = []\n",
    "        for i in range(len(grid)):\n",
    "            mark.append(['0'])\n",
    "            for j in range(len(grid[0])-1):\n",
    "                mark[i].append('0')\n",
    "\n",
    "        def dfs(mark,grid,x,y):\n",
    "            mark[x][y] = '1'\n",
    "            dx = [-1,1,0,0]\n",
    "            dy = [0,0,-1,1]\n",
    "            for i in range(4):\n",
    "                new_x = dx[i] + x\n",
    "                new_y = dy[i] + y\n",
    "                if new_x < 0 or new_y < 0 or new_x > len(grid)-1 or new_y > len(grid[0]) - 1:\n",
    "                    continue\n",
    "                if grid[new_x][new_y] == '1' and mark[new_x][new_y] == '0':\n",
    "                    dfs(mark,grid,new_x,new_y)\n",
    "        island = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                print(i,j)\n",
    "                print('m=',mark[i][j],'g=',grid[i][j])\n",
    "                if mark[i][j] == '0' and grid[i][j] == '1':\n",
    "                    print('x')\n",
    "                    dfs(mark,grid,i,j)\n",
    "                    island += 1\n",
    "        return island\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "            self.id = list(range(n))\n",
    "            self._sz = [1] * n\n",
    "            self.cc = n  # connected components\n",
    "\n",
    "    def _root(self, i):\n",
    "        j = i\n",
    "        while (j != self.id[j]):\n",
    "            self.id[j] = self.id[self.id[j]]\n",
    "            j = self.id[j]\n",
    "        return j\n",
    "\n",
    "    def find(self, p, q):\n",
    "        return self._root(p) == self._root(q)\n",
    "\n",
    "    def union(self, p, q):\n",
    "        i = self._root(p)\n",
    "        j = self._root(q)\n",
    "        if i == j:\n",
    "            return\n",
    "        if (self._sz[i] < self._sz[j]):\n",
    "            self.id[i] = j\n",
    "            self._sz[j] += self._sz[i]\n",
    "        else:\n",
    "            self.id[j] = i\n",
    "            self._sz[i] += self._sz[j]\n",
    "        self.cc -= 1\n",
    "class Solution:\n",
    "    def numIslands(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[str]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # grid=list(map(list,grid))\n",
    "        if not grid or not grid[0]:\n",
    "            return 0\n",
    "        # for item in grid:\n",
    "        #     print(item)\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        uf=UF(m*n)\n",
    "        node=lambda i, j:i*n+j\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==\"1\":\n",
    "                    if i>0 and grid[i-1][j]==\"1\":\n",
    "                        uf.union(node(i-1,j),node(i,j))\n",
    "                    if i<m-1 and grid[i+1][j]==\"1\":\n",
    "                        uf.union(node(i+1,j),node(i,j))\n",
    "                    if j>0 and grid[i][j-1]==\"1\":\n",
    "                        uf.union(node(i,j-1),node(i,j))\n",
    "                    if j<n-1 and grid[i][j+1]==\"1\":\n",
    "                        uf.union(node(i,j+1),node(i,j))\n",
    "                    # if i>0 and j>0 and grid[i-1][j-1]==\"1\":\n",
    "                    #     uf.union(node(i-1,j-1),node(i,j))\n",
    "                    # if i>0 and j<n-1 and grid[i-1][j+1]==\"1\":\n",
    "                    #     uf.union(node(i-1,j+1),node(i,j))\n",
    "                    # if i<m-1 and j>0 and grid[i+1][j ]==\"1\":\n",
    "                    #     uf.union(node(i+1,j),node(i,j))\n",
    "                    # if i<m-1 and j<n-1 and grid[i+1][j+1]==\"1\":\n",
    "                    #     uf.union(node(i+1,j+1),node(i,j))\n",
    "\n",
    "        # print(uf.id)\n",
    "        ans=set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==\"1\":\n",
    "                    # print([i,j],grid[i][j],uf._root(node(i, j)))\n",
    "                    # ans.append(uf._root(node(i, j)))\n",
    "                    ans.add(uf._root(node(i,j)))\n",
    "\n",
    "        print(ans)\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#coding=gbk\n",
    "from collections import deque\n",
    "class Solution:\n",
    "\tdef numIslands(self, grid):\n",
    "\t\tif not grid:return 0\n",
    "\t\t#bfs解法\n",
    "\t\tself.m,self.n=len(grid),len(grid[0])\n",
    "\t\tdict1={}\n",
    "\t\tfor i in range(self.m):\n",
    "\t\t\tfor j in range(self.n):\n",
    "\t\t\t\tif grid[i][j]=='1':\n",
    "\t\t\t\t\tdict1[(i,j)]=False\n",
    "\t\tdef bfs(i,j):\n",
    "\t\t\tQ=deque([(i,j)])\n",
    "\t\t\twhile Q:\n",
    "\t\t\t\tx,y=Q.popleft()\n",
    "\t\t\t\tif x-1>=0 and grid[x-1][y]=='1' and dict1[(x-1,y)]==False:\n",
    "\t\t\t\t\tdict1[(x-1,y)]=True\n",
    "\t\t\t\t\tQ.append((x-1,y))\n",
    "\t\t\t\tif x+1<self.m and grid[x+1][y]=='1' and dict1[(x+1,y)]==False:\n",
    "\t\t\t\t\tdict1[(x+1,y)]=True\n",
    "\t\t\t\t\tQ.append((x+1,y))\n",
    "\t\t\t\tif y-1>=0 and grid[x][y-1]=='1' and dict1[(x,y-1)]==False:\n",
    "\t\t\t\t\tdict1[(x,y-1)]=True\n",
    "\t\t\t\t\tQ.append((x,y-1))\n",
    "\t\t\t\tif y+1<self.n and grid[x][y+1]=='1' and dict1[(x,y+1)]==False:\n",
    "\t\t\t\t\tdict1[(x,y+1)]=True\n",
    "\t\t\t\t\tQ.append((x,y+1))\n",
    "\t\t\t\n",
    "\t\tre=0\n",
    "\t\tfor (x,y) in dict1:\n",
    "\t\t\tif not dict1[(x,y)]:\n",
    "\t\t\t\tdict1[(x,y)]=True\n",
    "\t\t\t\tbfs(x,y)\n",
    "\t\t\t\tre+=1\n",
    "\t\treturn re\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def BFS(self,grid,r,c,marked):\n",
    "        marked.add((r,c))\n",
    "        dr,dc = [-1,1,0,0],[0,0,-1,1]\n",
    "        frontier = [(r,c)]\n",
    "        while frontier:\n",
    "            next = []\n",
    "            for r,c in frontier:\n",
    "                for d in range(4):\n",
    "                    nr,nc = r+dr[d], c+dc[d]\n",
    "                    if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and (nr,nc) not in marked and grid[nr][nc] == '1':\n",
    "                        marked.add((nr,nc))\n",
    "                        next.append((nr,nc))\n",
    "            frontier = next\n",
    "            \n",
    "    def numIslands(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[str]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not grid:\n",
    "            return 0\n",
    "        res,marked = 0,set()\n",
    "        row,col = len(grid),len(grid[0])\n",
    "        for r in range(row):\n",
    "            for c in range(col):\n",
    "                if grid[r][c] == '1' and (r,c) not in marked:\n",
    "                    res += 1 \n",
    "                    self.BFS(grid,r,c,marked)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def BFS(self,grid,r,c,marked):\n",
    "        marked.add((r,c))\n",
    "        dr,dc = [-1,1,0,0],[0,0,-1,1]\n",
    "        frontier = [(r,c)]\n",
    "        while frontier:\n",
    "            next = []\n",
    "            for r,c in frontier:\n",
    "                for d in range(4):\n",
    "                    nr,nc = r+dr[d], c+dc[d]\n",
    "                    if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and (nr,nc) not in marked and grid[nr][nc] == '1':\n",
    "                        marked.add((nr,nc))\n",
    "                        next.append((nr,nc))\n",
    "            frontier = next\n",
    "            \n",
    "    def numIslands(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[str]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not grid:\n",
    "            return 0\n",
    "        res,marked = 0,set()\n",
    "        row,col = len(grid),len(grid[0])\n",
    "        for r in range(row):\n",
    "            for c in range(col):\n",
    "                if grid[r][c] == '1' and (r,c) not in marked:\n",
    "                    res += 1 \n",
    "                    self.BFS(grid,r,c,marked)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find(self, x, y, pred, grid):\n",
    "        # p, q = x, y\n",
    "        while (x != pred[x][y][0] or y != pred[x][y][1]):\n",
    "            x, y = pred[x][y][0], pred[x][y][1]\n",
    "        return x, y\n",
    "    def join(self, x1, y1, x2, y2, pred, grid):\n",
    "        p1, q1 = self.find(x1, y1, pred, grid)\n",
    "        p2, q2 = self.find(x2, y2, pred, grid)\n",
    "        # if p1 != p2 or q1 != q2:\n",
    "        pred[p2][q2] = [p1, q1]\n",
    "    def same(self, x1, y1, x2, y2, pred, grid):\n",
    "        return self.find(x1, y1, pred, grid) == self.find(x2, y2, pred, grid)\n",
    "    def numIslands(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[str]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(grid) == 0:\n",
    "            return 0\n",
    "        m = [[int(j) for j in i] for i in grid]\n",
    "        setnum = sum([sum(x) for x in m])\n",
    "        pred = [[[i, j] for j in range(len(grid[i]))] for i in range(len(grid))]\n",
    "        # print(pred)\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[i])):\n",
    "                # print(i, j)\n",
    "                if grid[i][j] == '1':\n",
    "                    if i == 0 and j == 0:\n",
    "                        continue;\n",
    "                    if j-1 >= 0 and grid[i][j-1] == '1':\n",
    "                        if not self.same(i, j, i, j-1, pred, grid):\n",
    "                            self.join(i, j, i, j-1, pred, grid)\n",
    "                            setnum -= 1\n",
    "                    if i-1 >= 0 and grid[i-1][j] == '1':\n",
    "                        if not self.same(i, j, i-1, j, pred, grid):\n",
    "                            self.join(i, j, i-1, j, pred, grid)\n",
    "                            setnum -= 1\n",
    "                    if j+1 <= len(grid[i])-1 and grid[i][j+1] == '1':\n",
    "                        if not self.same(i, j, i, j+1, pred, grid):\n",
    "                            self.join(i, j, i, j+1, pred, grid)\n",
    "                            setnum -= 1\n",
    "                    if i+1 <= len(grid)-1 and grid[i+1][j] == '1':\n",
    "                        if not self.same(i, j, i+1, j, pred, grid):\n",
    "                            self.join(i, j, i+1, j, pred, grid)\n",
    "                            setnum -= 1\n",
    "        return setnum\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: 'List[List[str]]') -> 'int':\n",
    "        \n",
    "        # 常见方法\n",
    "        def dfs(x,y):\n",
    "            if 0<=x<len(grid) and 0<=y<len(grid[0]) and grid[x][y]=='1':\n",
    "                grid[x][y]='N'\n",
    "                dfs(x-1,y)\n",
    "                dfs(x+1,y)\n",
    "                dfs(x,y-1)\n",
    "                dfs(x,y+1)\n",
    "        \n",
    "        count=0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j]=='1':\n",
    "                    dfs(i,j)\n",
    "                    count+=1\n",
    "        \n",
    "        return count\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def _numIslands(self, grid: List[List[str]]) -> int:\n",
    "        if not grid:\n",
    "            return 0\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        cnt = 0\n",
    "        \n",
    "        def dfs(i, j):\n",
    "            grid[i][j] = '0'\n",
    "            for x, y in [[-1, 0], [1, 0], [0, -1], [0, +1]]:\n",
    "                tmp_i = x + i\n",
    "                tmp_j = y + j\n",
    "                if 0 <= tmp_i < row and 0 <= tmp_j < col and grid[tmp_i][tmp_j] == '1':\n",
    "                    dfs(tmp_i, tmp_j)\n",
    "                    \n",
    "        \n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == '1':\n",
    "                    dfs(i, j)\n",
    "                    cnt += 1\n",
    "        return cnt\n",
    "    \n",
    "    def numIslands(self, grid):\n",
    "        from collections import deque\n",
    "        if not grid:\n",
    "            return 0\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        cnt = 0\n",
    "        \n",
    "        def dfs(i, j):\n",
    "            q = deque()\n",
    "            q.appendleft((i, j))\n",
    "            grid[i][j] = '0'\n",
    "            while q:\n",
    "                i, j = q.pop()\n",
    "                for x, y in [[-1, 0], [1, 0], [0, -1], [0, 1]]:\n",
    "                    tmp_i = i + x\n",
    "                    tmp_j = j + y\n",
    "                    if 0 <= tmp_i < row and 0 <= tmp_j < col and grid[tmp_i][tmp_j] == '1':\n",
    "                        grid[tmp_i][tmp_j] = '0'\n",
    "                        q.appendleft((tmp_i, tmp_j))\n",
    "        \n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == '1':\n",
    "                    dfs(i, j)\n",
    "                    cnt += 1\n",
    "        return cnt\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        # 先用bfs做\n",
    "        from collections import deque\n",
    "        r = len(grid)\n",
    "        if r == 0:\n",
    "            return 0\n",
    "        c = len(grid[0])\n",
    "        \n",
    "        cnt = 0\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if grid[i][j] == '1':\n",
    "                    cnt += 1\n",
    "                    grid[i][j] = '0'\n",
    "                    q = deque([(i, j)])\n",
    "                    while len(q) > 0:\n",
    "                        x, y = q.popleft()\n",
    "                        for a, b in [(x+1, y), (x-1, y),(x, y+1),(x, y-1)]:\n",
    "                            if 0 <= a <= r-1 and 0 <= b <= c-1 and grid[a][b] == '1':\n",
    "                                q.append([a, b])\n",
    "                                grid[a][b] = '0'\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        def bfs(row,col):\n",
    "            count = 0\n",
    "            if grid[row][col] == '1':  # 发现陆地\n",
    "                grid[row][col] = '0'  # 将其转为 ‘0’ 代表已经访问过\n",
    "                # 对发现的陆地进行扩张即执行 BFS，将与其相邻的陆地都标记为已访问\n",
    "                # 下面还是经典的 BFS 模板\n",
    "                land_positions.append([row, col])\n",
    "                \n",
    "                while len(land_positions) > 0:\n",
    "                    x, y = land_positions.popleft()\n",
    "                    for dx, dy in directs:\n",
    "                        new_x ,new_y=x+dx,y+dy # 进行四个方向的扩张\n",
    "                        # 判断有效性\n",
    "                        if 0 <= new_x < len(grid) and 0 <= new_y < len(grid[0]) and grid[new_x][new_y] == '1':\n",
    "                            grid[new_x][new_y] = '0'  # 因为可由 BFS 访问到，代表同属一块岛，将其置 ‘0’ 代表已访问过\n",
    "                            land_positions.append([new_x, new_y])\n",
    "                count += 1  # 结果加1      #发现一个1，就意味着至少有一个陆地了。            \n",
    "            return count\n",
    "        land_positions = collections.deque()\n",
    "        res=0\n",
    "        directs=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "        for row in range(len(grid)):\n",
    "            for col in range(len(grid[0])):\n",
    "                res+=bfs(row,col)\n",
    "        return res\n",
    "        '''\n",
    "        怎么不对？\n",
    "        count = 0\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        visited = [[False]*n for _ in range(m)]\n",
    "        for row in range(m):\n",
    "            for col in range(n):\n",
    "                if grid[row][col] == '1' and visited[row][col]==False  :  # 发现陆地\n",
    "                    \n",
    "                    visited[row][col]==True # 将其转为 ‘0’ 代表已经访问过\n",
    "                    # 对发现的陆地进行扩张即执行 BFS，将与其相邻的陆地都标记为已访问\n",
    "                    # 下面还是经典的 BFS 模板\n",
    "                    queue = collections.deque()\n",
    "                    queue.append([row, col])\n",
    "                    directs=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "                    while queue:\n",
    "                        x, y = queue.popleft()\n",
    "                        for dx, dy in directs:\n",
    "                            new_x ,new_y=x+dx,y+dy # 进行四个方向的扩张\n",
    "                            # 判断有效性\n",
    "                            if 0 <= new_x <m and 0 <= new_y < n and grid[new_x][new_y] == '1' and visited[new_x][new_y]==False:\n",
    "                                visited[new_x][new_y]==True\n",
    "                                  # 因为可由 BFS 访问到，代表同属一块岛，将其置 ‘0’ 代表已访问过\n",
    "                                queue.append([new_x, new_y])\n",
    "                    count += 1  # 结果加1      #发现一个1，就意味着至少有一个陆地了。            \n",
    "        return count\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, grid, r, c):\n",
    "        grid[r][c] = 0\n",
    "        nr, nc = len(grid), len(grid[0])\n",
    "        for x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:\n",
    "            if 0 <= x < nr and 0 <= y < nc and grid[x][y] == \"1\":\n",
    "                self.dfs(grid, x, y)\n",
    "\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        nr = len(grid)\n",
    "        if nr == 0:\n",
    "            return 0\n",
    "        nc = len(grid[0])\n",
    "\n",
    "        num_islands = 0\n",
    "        for r in range(nr):\n",
    "            for c in range(nc):\n",
    "                if grid[r][c] == \"1\":\n",
    "                    num_islands += 1\n",
    "                    self.dfs(grid, r, c)\n",
    "\n",
    "        return num_islands\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        \n",
    "        d = [[0,1], [1,0], [-1,0], [0,-1]]\n",
    "        res = 0\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "\n",
    "        def isArea(x, y):\n",
    "            return x >= 0 and y >=0 and x < m and y < n\n",
    "        \n",
    "        def __dfs(x, y):\n",
    "            # 从grid[x][y]的位置开始\n",
    "            visited[x][y] = True\n",
    "            # 向四个方向进行搜索遍历\n",
    "            for i in range(4):\n",
    "                new_x = x + d[i][0]\n",
    "                new_y = y + d[i][1]\n",
    "                if isArea(new_x, new_y) and not visited[new_x][new_y] and grid[new_x][new_y] == '1':\n",
    "                    __dfs(new_x, new_y)\n",
    "\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not visited[i][j] and grid[i][j] == '1':\n",
    "                    res += 1\n",
    "                    __dfs(i,j)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        r = len(grid)\n",
    "        c = len(grid[0])\n",
    "\n",
    "        def expand(x, y):\n",
    "            if grid[x][y]  == \"0\":\n",
    "                return\n",
    "            \n",
    "            grid[x][y] = \"0\"\n",
    "            # left\n",
    "            if y - 1 >= 0:\n",
    "                expand(x, y - 1)\n",
    "            if y + 1 < c:\n",
    "                expand(x, y + 1)\n",
    "            if x - 1 >= 0:\n",
    "                expand(x - 1, y)\n",
    "            if x + 1 < r:\n",
    "                expand(x + 1, y)\n",
    "\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if grid[i][j] == \"1\":\n",
    "                    res += 1\n",
    "                    expand(i, j)\n",
    "        print(grid)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, grid):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        self.count = 0\n",
    "        self.parent = [-1] * (m * n)\n",
    "        self.rank = [0] * (m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"1\":\n",
    "                    self.parent[i * n + j] = i * n + j\n",
    "                    self.count += 1\n",
    "    \n",
    "    def find(self, i):\n",
    "        if self.parent[i] != i:\n",
    "            self.parent[i] = self.find(self.parent[i])\n",
    "        return self.parent[i]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        rootx = self.find(x)\n",
    "        rooty = self.find(y)\n",
    "        if rootx != rooty:\n",
    "            if self.rank[rootx] < self.rank[rooty]:\n",
    "                rootx, rooty = rooty, rootx\n",
    "            self.parent[rooty] = rootx\n",
    "            if self.rank[rootx] == self.rank[rooty]:\n",
    "                self.rank[rootx] += 1\n",
    "            self.count -= 1\n",
    "    \n",
    "    def getCount(self):\n",
    "        return self.count\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        nr = len(grid)\n",
    "        if nr == 0:\n",
    "            return 0\n",
    "        nc = len(grid[0])\n",
    "\n",
    "        uf = UnionFind(grid)\n",
    "        num_islands = 0\n",
    "        for r in range(nr):\n",
    "            for c in range(nc):\n",
    "                if grid[r][c] == \"1\":\n",
    "                    grid[r][c] = \"0\"\n",
    "                    for x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:\n",
    "                        if 0 <= x < nr and 0 <= y < nc and grid[x][y] == \"1\":\n",
    "                            uf.union(r * nc + c, x * nc + y)\n",
    "        \n",
    "        return uf.getCount()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        if not grid: return 0\n",
    "        rownum = len(grid)\n",
    "        colnum = len(grid[0])\n",
    "        land = []\n",
    "        for i in range(rownum):\n",
    "            for j in range(colnum):\n",
    "                if grid[i][j]=='1':\n",
    "                    land.append((i,j))\n",
    "        if not land: return 0\n",
    "        count = 0\n",
    "        x = [1,0,0,-1]\n",
    "        y = [0,1,-1,0]\n",
    "        for a in land:\n",
    "            if grid[a[0]][a[1]]=='0':\n",
    "                continue\n",
    "            stack = [a]\n",
    "            grid[a[0]][a[1]]='0'\n",
    "            count += 1\n",
    "            while stack:\n",
    "                cur = stack.pop()\n",
    "                for b in range(4):\n",
    "                    if 0<=cur[0]+x[b]<rownum and 0<=cur[1]+y[b]<colnum and grid[cur[0]+x[b]][cur[1]+y[b]]=='1':\n",
    "                        stack.append((cur[0]+x[b],cur[1]+y[b]))\n",
    "                        grid[cur[0]+x[b]][cur[1]+y[b]]='0'\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        gird = grid\n",
    "        # y-m,x-n\n",
    "        m = len(gird)\n",
    "        n = len(gird[0])\n",
    "\n",
    "        # 初化root\n",
    "        root = []\n",
    "        k = 0\n",
    "        for y in range(m):\n",
    "            for x in range(n):  # 这么for y m写，巨好\n",
    "                root.append(k)\n",
    "                k += 1\n",
    "\n",
    "\n",
    "        def findRoot(cur):\n",
    "            \"\"\"\n",
    "            不改\n",
    "\n",
    "            :param 当前节点的index\n",
    "            :return: 当前节点的老子\n",
    "            \"\"\"\n",
    "            # 末1\n",
    "            if root[cur] == cur:\n",
    "                return cur\n",
    "\n",
    "            # 下\n",
    "            if root[cur] != cur:  # 可无，写上易懂些\n",
    "                root[cur] = findRoot(root[cur])\n",
    "                return root[cur]\n",
    "\n",
    "            # mr\n",
    "\n",
    "\n",
    "\n",
    "        def connect(cur, new, a):\n",
    "            \"\"\"\n",
    "            改root数组\n",
    "\n",
    "            :param cur: 当前index\n",
    "            :param new: 四周index\n",
    "            \"\"\"\n",
    "\n",
    "\n",
    "            # 找当前的老子1\n",
    "            rot1 = findRoot(cur)\n",
    "\n",
    "            # 找4向的老子2\n",
    "            rot2 = findRoot(new)\n",
    "\n",
    "            # 如果老子同，已是一家不管\n",
    "\n",
    "            # 如果老子不同，只改1个值【老子1变成老子2的老子】\n",
    "            if rot1 != rot2:\n",
    "                # rot2的新老子是rot1\n",
    "                root[rot2] = rot1\n",
    "                a[0] -= 1\n",
    "\n",
    "\n",
    "        # MAIN\n",
    "\n",
    "\n",
    "        count = m * n\n",
    "        a = [count]\n",
    "        for y in range(m):\n",
    "            for x in range(n):\n",
    "                # 当前坐标转index\n",
    "                cur = x + y * n\n",
    "                if gird[y][x] == '0':\n",
    "                    a[0] -= 1\n",
    "                elif gird[y][x] == '1':  # 当前为1，4向未知\n",
    "                    # print('_______________', cur, '号开始_________________')\n",
    "                    # # 上\n",
    "                    # if y - 1 >= 0 and y - 1 < m and x >= 0 and x < n:\n",
    "                    #     if gird[y - 1][x] == '1':\n",
    "                    #         # 上的坐标转index\n",
    "                    #         up = (y - 1) * n + x\n",
    "                    #         connect(cur, up,a)\n",
    "                    #         # print('连上', up, '后：', root)\n",
    "                    #         # print('           [0, 1, 2, 3, 4, 5, 6, 7, 8]')\n",
    "\n",
    "                    # 下\n",
    "                    if y + 1 >= 0 and y + 1 < m and x >= 0 and x < n:\n",
    "                        if gird[y + 1][x] == '1':\n",
    "                            # 下的坐标转index\n",
    "                            down = (y + 1) * n + x\n",
    "                            connect(cur, down,a)\n",
    "                            # print('连下', down, '后：', root)\n",
    "                            # print('           [0, 1, 2, 3, 4, 5, 6, 7, 8]')\n",
    "\n",
    "                    # # 左\n",
    "                    # if y >= 0 and y < m and x - 1 >= 0 and x - 1 < n:\n",
    "                    #     if gird[y][x - 1] == '1':\n",
    "                    #         # 左的坐标转index\n",
    "                    #         left = y * n + x - 1\n",
    "                    #         connect(cur, left,a)\n",
    "                    #         # print('连左', left, '后：', root)\n",
    "                    #         # print('           [0, 1, 2, 3, 4, 5, 6, 7, 8]')\n",
    "\n",
    "                    # 右\n",
    "                    if y >= 0 and y < m and x + 1 >= 0 and x + 1 < n:\n",
    "                        if gird[y][x + 1] == '1':\n",
    "                            # 右的坐标转index\n",
    "                            right = y * n + x + 1\n",
    "                            connect(cur, right,a)\n",
    "                            # print('连右', right, '后：', root)\n",
    "                            # print('           [0, 1, 2, 3, 4, 5, 6, 7, 8]')\n",
    "\n",
    "        # print(a[0])\n",
    "        return a[0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        # dfs  并查集\n",
    "        def union(p, i, j):\n",
    "            p1 = parent(p, i)\n",
    "            p2 = parent(p, j)\n",
    "            if p1 == p2:\n",
    "                return 1\n",
    "            p[p2] = p1\n",
    "        def parent(p, i):\n",
    "            root = i\n",
    "            while p[root] != root:\n",
    "                root = p[root]\n",
    "            while p[i] != i:\n",
    "                x = i; i = p[i]; p[x] = root\n",
    "            return root\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        count, space = m * n, 0\n",
    "        p = [i for i in range(m*n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '1':\n",
    "                    for di, dj in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:\n",
    "                        if 0 <= di < m and 0 <= dj < n and grid[di][dj] == '1':\n",
    "                            a = union(p, i*n + j, di*n + dj)\n",
    "                            if a != 1:\n",
    "                                count -= 1\n",
    "                else:\n",
    "                    space += 1\n",
    "        return count - space"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        f = {}\n",
    "\n",
    "        def find(x):\n",
    "            f.setdefault(x, x)\n",
    "            if f[x] != x:\n",
    "                f[x] = find(f[x])\n",
    "            return f[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            f[find(x)] = find(y)\n",
    "\n",
    "        if not grid: return 0\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == \"1\":\n",
    "                    for x, y in [[-1, 0], [0, -1]]:\n",
    "                        tmp_i = i + x\n",
    "                        tmp_j = j + y\n",
    "                        if 0 <= tmp_i < row and 0 <= tmp_j < col and grid[tmp_i][tmp_j] == \"1\":\n",
    "                            union(tmp_i * row + tmp_j, i * row + j)\n",
    "        print(f)\n",
    "        res = set()\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == \"1\":\n",
    "                    res.add(find((i * row + j)))\n",
    "        return len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        if grid is None:\n",
    "            return 0\n",
    "        r = len(grid)\n",
    "        c = len(grid[0])\n",
    "        count = 0\n",
    "        trace = []\n",
    "        def dfs(grid, r, c):\n",
    "            trace.append([r, c])\n",
    "            grid[r][c] = '0'\n",
    "            nr = len(grid)\n",
    "            nc = len(grid[0])\n",
    "            for i, j in [(r-1, c),(r, c-1),(r+1, c),(r, c+1)]:\n",
    "                if 0<=i<nr and 0<=j<nc and grid[i][j]=='1':\n",
    "                    dfs(grid, i, j)\n",
    "        for r in range(len(grid)):\n",
    "            for c in range(len(grid[0])):\n",
    "                if grid[r][c] == '1':\n",
    "                    print('r = %s, c= %s'%(r, c))\n",
    "                    count += 1\n",
    "                    dfs(grid, r, c)\n",
    "        print(trace)\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class BFS:\n",
    "    \"\"\"bfs框架(以队列实现bfs)\"\"\"\n",
    "\n",
    "    def __init__(self):\n",
    "        # 用集合保存已遍历过的元素\n",
    "        self.explored = set()\n",
    "\n",
    "        # bfs搜索的目标元素\n",
    "        self.goal = 'the expect object of this question'\n",
    "\n",
    "    def bfs_search(self, init_elem, is_goal: callable, get_next_valid_elems: callable):\n",
    "        \"\"\"bfs搜索，本框架借助队列实现bfs，bfs亦可通过递归调用自身实现，本框架暂不实现\n",
    "        init_elem:初始元素\n",
    "        is_goal(回调函数)：判断当前值是否为目标值\n",
    "        get_next_valid_elems(回调函数)：下一个位置的可能元素集合\n",
    "        \"\"\"\n",
    "        # 队列保存需要遍历的元素\n",
    "        need_explore = deque([init_elem])\n",
    "        self.explored.add(init_elem)\n",
    "        # 队列不为空就一直处理，直至为空\n",
    "        while need_explore:\n",
    "            # 获取队列当前需要处理的元素\n",
    "            now_elem = need_explore.popleft()\n",
    "\n",
    "            # 判断当前元素是否为目标元素\n",
    "            if is_goal(elem=now_elem, goal=self.goal):\n",
    "                break  # 根据题目要求修改goal目标值，break表示找到目标元素就终止寻找（当前岛屿题目无须找目标值）\n",
    "\n",
    "            # 探索下个位置的元素，并将其入队列\n",
    "            for next_elem in get_next_valid_elems(now_elem):\n",
    "                # 将待处理的元素入队列\n",
    "                need_explore.append(next_elem)\n",
    "                # 将已处理过的元素加入集合，防止重复处理该元素\n",
    "                self.explored.add(next_elem)\n",
    "\n",
    "            \"\"\"\n",
    "            代码执行到这里表示当前元素的处理已完毕，但是还没找到目标值，因此需要去遍历下一个元素进行处理，\n",
    "            下一元素已保存到队列里，因此下次while循环对队列进行popleft()就得到下个要处理的元素,\n",
    "            本框架和dfs的区别其实就在从左取元素还是从右取元素\n",
    "            \"\"\"\n",
    "\n",
    "    @staticmethod\n",
    "    def is_goal(elem, goal):\n",
    "        \"\"\"判断当前元素是否为目标元素\n",
    "        elem:当前元素\n",
    "        goal:目标值\n",
    "        \"\"\"\n",
    "        return elem == goal\n",
    "\n",
    "    def get_next_valid_elems(self, now_elem):\n",
    "        \"\"\"获取当前元素的下一位置元素\n",
    "        now_elem:当前元素\n",
    "        explored:已处理过的元素集合（验证下一元素有效性时使用）\"\"\"\n",
    "        pass\n",
    "\n",
    "\n",
    "class Solution(BFS):\n",
    "    \"\"\"借助框架求解\"\"\"\n",
    "\n",
    "    def __init__(self):\n",
    "        # 本岛屿问题无需找目标值，主要是求bfs次数\n",
    "        self.goal = \"this question not need goal\"\n",
    "        # 网格\n",
    "        self.grid = None\n",
    "        # 网格行数\n",
    "        self.row_nums = None\n",
    "        # 网格列数\n",
    "        self.column_nums = None\n",
    "        super().__init__()\n",
    "\n",
    "    def numIslands(self, grid) -> int:\n",
    "        \"\"\"获取岛屿数量\"\"\"\n",
    "        self.grid = grid\n",
    "        self.row_nums = len(self.grid)\n",
    "        if self.row_nums == 0:\n",
    "            return 0\n",
    "        self.column_nums = len(self.grid[0])\n",
    "\n",
    "        # 岛屿初始数量\n",
    "        num_islands = 0\n",
    "        for r in range(self.row_nums):\n",
    "            for c in range(self.column_nums):\n",
    "                if self.grid[r][c] == \"1\" and (r, c) not in self.explored:\n",
    "                    # 本问题可转化为求bfs的次数，进行次数统计即为岛的数量\n",
    "                    num_islands += 1\n",
    "                    self.bfs_search(init_elem=(r, c),\n",
    "                                    is_goal=self.is_goal,\n",
    "                                    get_next_valid_elems=self.get_next_valid_elems)\n",
    "\n",
    "        return num_islands\n",
    "\n",
    "    def is_goal(self, elem, goal):\n",
    "        \"\"\"判断当前元素是否为目标元素\n",
    "        elem:当前元素\n",
    "        goal:目标值\n",
    "        \"\"\"\n",
    "        return elem == goal\n",
    "\n",
    "    def get_next_valid_elems(self, now_elem):\n",
    "        \"\"\"获取当前元素的下一位置元素\n",
    "        now_elem:当前元素\n",
    "        \"\"\"\n",
    "        row = now_elem[0]\n",
    "        col = now_elem[1]\n",
    "        next_elems = [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]\n",
    "        next_valid_elems = []\n",
    "        for next_elem in next_elems:\n",
    "            x = next_elem[0]\n",
    "            y = next_elem[1]\n",
    "            # 判断元素有效性\n",
    "            if 0 <= x < self.row_nums and 0 <= y < self.column_nums and self.grid[x][y] == \"1\" \\\n",
    "                    and (x, y) not in self.explored:\n",
    "                next_valid_elems.append((x, y))\n",
    "        return next_valid_elems"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        # 非递归的BFS/DFS实现\n",
    "        # 如果是DFS，就使用栈，每次弹出栈顶\n",
    "        # 如果是BFS，就用队列，每次取出队头，但是建议用DFS，因为每次pop(0)消耗很高\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        island_count = 0\n",
    "        for ii in range(m):\n",
    "            for jj in range(n):\n",
    "                if grid[ii][jj] == \"1\":\n",
    "                    # 查找到一个一个1 就把他的上下左右的1压入栈\n",
    "                    places = [(ii,jj)]\n",
    "                    while places:\n",
    "                        i,j = places.pop()\n",
    "                        grid[i][j] = \"0\"\n",
    "                        if i+1<m and grid[i+1][j]==\"1\":\n",
    "                            places.append((i+1,j))\n",
    "                        if i-1>=0 and grid[i-1][j]==\"1\":\n",
    "                            places.append((i-1,j))\n",
    "                        if j+1<n and grid[i][j+1]==\"1\":\n",
    "                            places.append((i,j+1))\n",
    "                        if j-1>=0 and grid[i][j-1]==\"1\":\n",
    "                            places.append((i,j-1))\n",
    "                    island_count += 1\n",
    "        return island_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        nr = len(grid)\n",
    "        if nr == 0:\n",
    "            return 0\n",
    "        nc = len(grid[0])\n",
    "        num_islands = 0\n",
    "        for r in range(nr):\n",
    "            for c in range(nc):\n",
    "                if grid[r][c] == '1':\n",
    "                    num_islands += 1\n",
    "                    grid[r][c] = \"0\"\n",
    "                    nerghbors = collections.deque([(r,c)])\n",
    "                    while nerghbors:\n",
    "                        row, col = nerghbors.popleft()\n",
    "                        for x, y in [(row-1, col),(row+1, col),(row,col-1),(row,col+1)]:\n",
    "                            if 0<=x<nr and 0<=y<nc and grid[x][y]==\"1\":\n",
    "                                nerghbors.append((x,y))\n",
    "                                grid[x][y]=\"0\"\n",
    "        return num_islands            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid):\n",
    "        row, col, ret = len(grid), len(grid[0]), 0\n",
    "\n",
    "        def dfs(x, y):\n",
    "            grid[x][y] = '0'\n",
    "            for c in [[0, 1], [0, -1], [1, 0], [-1, 0]]:\n",
    "                nx, ny = x + c[0], y + c[1]\n",
    "                if 0 <= nx < row and 0 <= ny < col and grid[nx][ny] == '1':\n",
    "                    dfs(nx, ny)\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == '1':\n",
    "                    dfs(i, j)\n",
    "                    ret += 1\n",
    "        return ret\n",
    "\n",
    "\n",
    "    # def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        # 深度优先\n",
    "        # def dfs(grid, i, j):\n",
    "        #     if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == '0':\n",
    "        #         return\n",
    "        #     grid[i][j] = '0'\n",
    "        #     dfs(grid, i+1, j)\n",
    "        #     dfs(grid, i-1, j)\n",
    "        #     dfs(grid, i, j+1)\n",
    "        #     dfs(grid, i, j-1)\n",
    "\n",
    "        # 广度优先\n",
    "        # def bfs(grid, i, j):\n",
    "        #     queue = deque([(i, j)])\n",
    "        #     while queue:\n",
    "        #         x, y = queue.popleft()\n",
    "        #         if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[0]) or grid[x][y] == '0':\n",
    "        #             continue\n",
    "        #         grid[x][y] = '0'\n",
    "        #         queue.append((x+1, y))\n",
    "        #         queue.append((x-1, y))\n",
    "        #         queue.append((x, y+1))\n",
    "        #         queue.append((x, y-1))\n",
    "\n",
    "        # if not grid:\n",
    "        #     return 0\n",
    "\n",
    "        # count = 0\n",
    "        # for i in range(len(grid)):\n",
    "        #     for j in range(len(grid[0])):\n",
    "        #         if grid[i][j] == '1':\n",
    "        #             count += 1\n",
    "        #             # dfs(grid, i, j)\n",
    "        #             bfs(grid, i, j)\n",
    "\n",
    "        # return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]\n",
    "        res = 0\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        visit = [[False] * n for _ in range(m)]\n",
    "\n",
    "        def dfs(x, y):\n",
    "            for d in directions:\n",
    "                next_i = x + d[0]\n",
    "                next_j = y + d[1]\n",
    "\n",
    "                if next_i < 0 or next_i >= m or next_j < 0 or next_j >= n:\n",
    "                    continue\n",
    "                if not visit[next_i][next_j] and grid[next_i][next_j] == \"1\":\n",
    "                    visit[next_i][next_j] = True\n",
    "                    dfs(next_i, next_j)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not visit[i][j] and grid[i][j] == \"1\":\n",
    "                    visit[i][j] = True\n",
    "                    dfs(i, j)\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [[True for _ in range(n+2)]for j in range(m+2)]\n",
    "\n",
    "        for i in range(m+2):\n",
    "            dp[i][0] = False\n",
    "            dp[i][n+1] = False\n",
    "        for j in range(n+2):\n",
    "            dp[0][j] = False\n",
    "            dp[m+1][j] = False\n",
    "        \n",
    "        def check(i, j):\n",
    "            dp[i][j] = False\n",
    "            directions = [[0,1],[0,-1],[1,0],[-1,0]]\n",
    "            for choice in directions:\n",
    "                xi, xj = i+choice[0], j+choice[1]\n",
    "                if 0 < xi < m+1 and 0 < xj < n+1 and grid[xi-1][xj-1] == '1' and dp[xi][xj]:\n",
    "                    check(xi,xj)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if grid[i-1][j-1] == '1' and dp[i][j]:\n",
    "                    check(i,j)\n",
    "                    ans += 1\n",
    "        return ans \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        cnt = 0\n",
    "        idx = 1\n",
    "        mark = [0]*(m*n+1)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                grid[i][j] = int(grid[i][j])\n",
    "                if grid[i][j] == 1:\n",
    "                    if i-1>=0 and grid[i-1][j]>0 and j-1>=0 and grid[i][j-1]>0:\n",
    "                        tmp1 = grid[i-1][j]\n",
    "                        while mark[tmp1] != 0:\n",
    "                            tmp1 = mark[tmp1]\n",
    "                        tmp2 = grid[i][j-1]\n",
    "                        while mark[tmp2] != 0:\n",
    "                            tmp2 = mark[tmp2]\n",
    "                        if tmp1==tmp2:\n",
    "                            grid[i][j] = tmp1\n",
    "                        elif tmp1<tmp2:\n",
    "                            grid[i][j] = tmp1\n",
    "                            mark[tmp2] = tmp1\n",
    "                        else:\n",
    "                            grid[i][j] = tmp2\n",
    "                            mark[tmp1] = tmp2\n",
    "                    elif i-1>=0 and grid[i-1][j]>0:\n",
    "                        grid[i][j] = grid[i-1][j]\n",
    "                    elif j-1>=0 and grid[i][j-1]>0:\n",
    "                        grid[i][j] = grid[i][j-1]\n",
    "                    else:\n",
    "                        grid[i][j] = idx\n",
    "                        idx += 1\n",
    "        res = []\n",
    "        for i in range(1,idx):\n",
    "            tmp = i\n",
    "            while mark[tmp] != 0:\n",
    "                tmp = mark[tmp]\n",
    "            if tmp not in res:\n",
    "                res.append(tmp)\n",
    "        print(idx,mark,grid)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, grid, i, j, idx):\n",
    "        if int(grid[i][j]) <= 0:\n",
    "            return\n",
    "        grid[i][j] = -idx\n",
    "        if i-1 >= 0:\n",
    "            self.dfs(grid, i-1, j, idx)\n",
    "        if j-1 >= 0:\n",
    "            self.dfs(grid, i, j-1, idx)\n",
    "        if i+1 < len(grid):\n",
    "            self.dfs(grid, i+1, j, idx)\n",
    "        if j+1 < len(grid[0]):\n",
    "            self.dfs(grid, i, j+1, idx)\n",
    "\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        idx = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if int(grid[i][j]) <= 0:\n",
    "                    continue\n",
    "                idx += 1 \n",
    "                self.dfs(grid, i, j, idx)\n",
    "        return idx\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, grid):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        self.count = 0\n",
    "        self.parent = [-1] * (m * n)\n",
    "        # self.rank = [0] * (m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"1\":\n",
    "                    self.parent[i * n + j] = i * n + j\n",
    "                    self.count += 1\n",
    "    \n",
    "    def find(self, i):\n",
    "        if self.parent[i] != i:\n",
    "            self.parent[i] = self.find(self.parent[i])\n",
    "        return self.parent[i]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        rootx = self.find(x)\n",
    "        rooty = self.find(y)\n",
    "        if rootx != rooty:\n",
    "            # if self.rank[rootx] < self.rank[rooty]:\n",
    "            #     rootx, rooty = rooty, rootx\n",
    "            self.parent[rooty] = rootx\n",
    "            # if self.rank[rootx] == self.rank[rooty]:\n",
    "            #     self.rank[rootx] += 1\n",
    "            self.count -= 1\n",
    "    \n",
    "    def getCount(self):\n",
    "        return self.count\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        nr = len(grid)\n",
    "        if nr == 0:\n",
    "            return 0\n",
    "        nc = len(grid[0])\n",
    "\n",
    "        uf = UnionFind(grid)\n",
    "        num_islands = 0\n",
    "        for r in range(nr):\n",
    "            for c in range(nc):\n",
    "                if grid[r][c] == \"1\":\n",
    "                    grid[r][c] = \"0\"\n",
    "                    for x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:\n",
    "                        if 0 <= x < nr and 0 <= y < nc and grid[x][y] == \"1\":\n",
    "                            uf.union(r * nc + c, x * nc + y)\n",
    "        \n",
    "        return uf.getCount()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, grid):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        self.count = 0\n",
    "        self.parent = [-1] * (m * n)\n",
    "        self.rank = [0] * (m * n)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"1\":\n",
    "                    index = i * n + j\n",
    "                    self.parent[index] = index\n",
    "                    self.count += 1\n",
    "\n",
    "    def find(self, i):\n",
    "        if self.parent[i] != i:\n",
    "            self.parent[i] = self.find(self.parent[i])\n",
    "        return self.parent[i]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX != rootY:\n",
    "            if self.rank[rootX] < self.rank[rootY]:\n",
    "                self.parent[rootX] = rootY\n",
    "            elif self.rank[rootX] > self.rank[rootY]:\n",
    "                self.parent[rootY] = rootX\n",
    "            else:\n",
    "                self.parent[rootY] = rootX\n",
    "                self.rank[rootX] += 1\n",
    "            self.count -= 1\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid):\n",
    "        if not grid:\n",
    "            return 0\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        uf = UnionFind(grid)\n",
    "        \n",
    "        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"1\":\n",
    "                    for dx, dy in directions:\n",
    "                        ni, nj = i + dx, j + dy\n",
    "                        if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == \"1\":\n",
    "                            uf.union(i * n + j, ni * n + nj)\n",
    "        \n",
    "        return uf.count\n",
    "\n",
    "\n",
    "    # def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        # 深度优先\n",
    "        # def dfs(grid, i, j):\n",
    "        #     if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == '0':\n",
    "        #         return\n",
    "        #     grid[i][j] = '0'\n",
    "        #     dfs(grid, i+1, j)\n",
    "        #     dfs(grid, i-1, j)\n",
    "        #     dfs(grid, i, j+1)\n",
    "        #     dfs(grid, i, j-1)\n",
    "\n",
    "        # 广度优先\n",
    "        # def bfs(grid, i, j):\n",
    "        #     queue = deque([(i, j)])\n",
    "        #     while queue:\n",
    "        #         x, y = queue.popleft()\n",
    "        #         if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[0]) or grid[x][y] == '0':\n",
    "        #             continue\n",
    "        #         grid[x][y] = '0'\n",
    "        #         queue.append((x+1, y))\n",
    "        #         queue.append((x-1, y))\n",
    "        #         queue.append((x, y+1))\n",
    "        #         queue.append((x, y-1))\n",
    "\n",
    "        # if not grid:\n",
    "        #     return 0\n",
    "\n",
    "        # count = 0\n",
    "        # for i in range(len(grid)):\n",
    "        #     for j in range(len(grid[0])):\n",
    "        #         if grid[i][j] == '1':\n",
    "        #             count += 1\n",
    "        #             # dfs(grid, i, j)\n",
    "        #             bfs(grid, i, j)\n",
    "\n",
    "        # return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, grid):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        self.count = 0\n",
    "        self.parent = [-1] * (m * n)\n",
    "        self.rank = [0] * (m * n)\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"1\":\n",
    "                    index = i * n + j\n",
    "                    self.parent[index] = index\n",
    "                    self.count += 1\n",
    "\n",
    "    def find(self, i):\n",
    "        if self.parent[i] != i:\n",
    "            self.parent[i] = self.find(self.parent[i])\n",
    "        return self.parent[i]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX != rootY:\n",
    "            if self.rank[rootX] < self.rank[rootY]:\n",
    "                self.parent[rootX] = rootY\n",
    "            elif self.rank[rootX] > self.rank[rootY]:\n",
    "                self.parent[rootY] = rootX\n",
    "            else:\n",
    "                self.parent[rootY] = rootX\n",
    "                self.rank[rootX] += 1\n",
    "            self.count -= 1\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid):\n",
    "        if not grid:\n",
    "            return 0\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        uf = UnionFind(grid)\n",
    "        \n",
    "        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"1\":\n",
    "                    for dx, dy in directions:\n",
    "                        ni, nj = i + dx, j + dy\n",
    "                        if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == \"1\":\n",
    "                            uf.union(i * n + j, ni * n + nj)\n",
    "        \n",
    "        return uf.count\n",
    "\n",
    "\n",
    "    # def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        # 深度优先\n",
    "        # def dfs(grid, i, j):\n",
    "        #     if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == '0':\n",
    "        #         return\n",
    "        #     grid[i][j] = '0'\n",
    "        #     dfs(grid, i+1, j)\n",
    "        #     dfs(grid, i-1, j)\n",
    "        #     dfs(grid, i, j+1)\n",
    "        #     dfs(grid, i, j-1)\n",
    "\n",
    "        # 广度优先\n",
    "        # def bfs(grid, i, j):\n",
    "        #     queue = deque([(i, j)])\n",
    "        #     while queue:\n",
    "        #         x, y = queue.popleft()\n",
    "        #         if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[0]) or grid[x][y] == '0':\n",
    "        #             continue\n",
    "        #         grid[x][y] = '0'\n",
    "        #         queue.append((x+1, y))\n",
    "        #         queue.append((x-1, y))\n",
    "        #         queue.append((x, y+1))\n",
    "        #         queue.append((x, y-1))\n",
    "\n",
    "        # if not grid:\n",
    "        #     return 0\n",
    "\n",
    "        # count = 0\n",
    "        # for i in range(len(grid)):\n",
    "        #     for j in range(len(grid[0])):\n",
    "        #         if grid[i][j] == '1':\n",
    "        #             count += 1\n",
    "        #             # dfs(grid, i, j)\n",
    "        #             bfs(grid, i, j)\n",
    "\n",
    "        # return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFindQuickUnion(object):\n",
    "    def __init__(self, n: int):\n",
    "        self.parent_seq = [i for i in range(n)]\n",
    "        self.count = n\n",
    "\n",
    "    def find(self, x: int):\n",
    "        elem, parent = x, self.parent_seq[x]\n",
    "        # 隔代压缩\n",
    "        while elem != parent:\n",
    "            self.parent_seq[elem] = self.parent_seq[parent]\n",
    "            elem = self.parent_seq[elem]\n",
    "            parent = self.parent_seq[elem]\n",
    "        return elem\n",
    "\n",
    "    def is_connected(self, x: int, y: int):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def union(self, x: int, y: int):\n",
    "        root_x, root_y = self.find(x), self.find(y)\n",
    "        if root_x != root_y:\n",
    "            self.parent_seq[root_x] = root_y\n",
    "            self.count -= 1\n",
    "\n",
    "    def get_count(self):\n",
    "        return self.count\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        uf = UnionFindQuickUnion(m*n)\n",
    "        ij2id = lambda x, y: x * n + y\n",
    "        cnt_1 = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                p = int(grid[i][j])\n",
    "                if not p:\n",
    "                    continue\n",
    "                \n",
    "                cnt_1 += 1\n",
    "                if j <= n - 2:\n",
    "                    p_right = int(grid[i][j+1])\n",
    "                    if p_right == 1:\n",
    "                        uf.union(\n",
    "                            ij2id(i, j), ij2id(i, j+1)\n",
    "                        )\n",
    "                \n",
    "                if i <= m - 2:\n",
    "                    p_down = int(grid[i+1][j])\n",
    "                    if p_down:\n",
    "                        uf.union(\n",
    "                            ij2id(i, j), ij2id(i+1, j)\n",
    "                        )\n",
    "        \n",
    "        cur_parts = uf.get_count()\n",
    "        shrink = m * n - cur_parts\n",
    "        islands = cnt_1 - shrink\n",
    "        # print(f\"cur_parts: {cur_parts}, shrink: {shrink}, cnt_1: {cnt_1}\")\n",
    "        return islands\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, grid, r, c):\n",
    "        grid[r][c] = [\"0\"]\n",
    "        nr, nc = len(grid), len(grid[0])\n",
    "        for x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:\n",
    "            if 0 <= x< nr and 0 <= y < nc and grid[x][y] == \"1\":\n",
    "                self.dfs(grid, x, y)\n",
    "        \n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        nr = len(grid)\n",
    "        if nr==0:\n",
    "            return 0\n",
    "        nc = len(grid[0])\n",
    "        res = 0\n",
    "        for i in range(nr):\n",
    "            for j in range(nc):\n",
    "                if grid[i][j] == \"1\":\n",
    "                    res += 1\n",
    "                    self.dfs(grid, i, j)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.count = n\n",
    "        self.parent = list(range(n))\n",
    "        self.rank = [0] * n\n",
    "\n",
    "    def find(self, p):\n",
    "        if self.parent[p] != p:\n",
    "            self.parent[p] = self.find(self.parent[p])\n",
    "        return self.parent[p]\n",
    "\n",
    "    def union(self, p, q):\n",
    "        root_p = self.find(p)\n",
    "        root_q = self.find(q)\n",
    "        if root_p != root_q:\n",
    "            if self.rank[root_p] > self.rank[root_q]:\n",
    "                self.parent[root_q] = root_p\n",
    "            else:\n",
    "                self.parent[root_p] = root_q\n",
    "                if self.rank[root_p] == self.rank[root_q]:\n",
    "                    self.rank[root_q] += 1\n",
    "            self.count -= 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        if not grid or not grid[0]:\n",
    "            return 0\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        uf = UnionFind(m * n)\n",
    "        \n",
    "        def index(i, j):\n",
    "            return i * n + j\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '1':\n",
    "                    if i > 0 and grid[i-1][j] == '1':\n",
    "                        uf.union(index(i, j), index(i-1, j))\n",
    "                    if i < m - 1 and grid[i+1][j] == '1':\n",
    "                        uf.union(index(i, j), index(i+1, j))\n",
    "                    if j > 0 and grid[i][j-1] == '1':\n",
    "                        uf.union(index(i, j), index(i, j-1))\n",
    "                    if j < n - 1 and grid[i][j+1] == '1':\n",
    "                        uf.union(index(i, j), index(i, j+1))\n",
    "        \n",
    "        zero_count = sum(grid[i][j] == '0' for i in range(m) for j in range(n))\n",
    "        return uf.count - zero_count\n",
    "\n",
    "    # def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        # 深度优先\n",
    "        # def dfs(grid, i, j):\n",
    "        #     if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == '0':\n",
    "        #         return\n",
    "        #     grid[i][j] = '0'\n",
    "        #     dfs(grid, i+1, j)\n",
    "        #     dfs(grid, i-1, j)\n",
    "        #     dfs(grid, i, j+1)\n",
    "        #     dfs(grid, i, j-1)\n",
    "\n",
    "        # 广度优先\n",
    "        # def bfs(grid, i, j):\n",
    "        #     queue = deque([(i, j)])\n",
    "        #     while queue:\n",
    "        #         x, y = queue.popleft()\n",
    "        #         if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[0]) or grid[x][y] == '0':\n",
    "        #             continue\n",
    "        #         grid[x][y] = '0'\n",
    "        #         queue.append((x+1, y))\n",
    "        #         queue.append((x-1, y))\n",
    "        #         queue.append((x, y+1))\n",
    "        #         queue.append((x, y-1))\n",
    "\n",
    "        # if not grid:\n",
    "        #     return 0\n",
    "\n",
    "        # count = 0\n",
    "        # for i in range(len(grid)):\n",
    "        #     for j in range(len(grid[0])):\n",
    "        #         if grid[i][j] == '1':\n",
    "        #             count += 1\n",
    "        #             # dfs(grid, i, j)\n",
    "        #             bfs(grid, i, j)\n",
    "\n",
    "        # return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        def find(x) :\n",
    "            if p[x] != x :\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "        def union(x, y) : \n",
    "            px, py = find(x), find(y) \n",
    "            if px == py :\n",
    "                return \n",
    "            p[px] = py\n",
    "        leny = len(grid)\n",
    "        lenx = len(grid[0])\n",
    "        p = list(range(lenx * leny))\n",
    "        for i, row in enumerate(grid) :\n",
    "            for j, v in enumerate(row) :\n",
    "                if v == '1' :\n",
    "                    for a, b in [[0, -1], [-1, 0]] :\n",
    "                        x, y = i + a, j + b\n",
    "                        if 0 <= x < leny and 0 <= y < lenx and grid[x][y] == '1':\n",
    "                            union(i * lenx + j, x * lenx + y)\n",
    "        ans = 0\n",
    "        havesee = dict()\n",
    "        for i in range(lenx * leny) :\n",
    "            if find(i) not in havesee and grid[i // lenx][i % lenx] != '0':\n",
    "                havesee[p[i]] = 1\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "    # def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        # 深度优先\n",
    "        # def dfs(grid, i, j):\n",
    "        #     if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == '0':\n",
    "        #         return\n",
    "        #     grid[i][j] = '0'\n",
    "        #     dfs(grid, i+1, j)\n",
    "        #     dfs(grid, i-1, j)\n",
    "        #     dfs(grid, i, j+1)\n",
    "        #     dfs(grid, i, j-1)\n",
    "\n",
    "        # 广度优先\n",
    "        # def bfs(grid, i, j):\n",
    "        #     queue = deque([(i, j)])\n",
    "        #     while queue:\n",
    "        #         x, y = queue.popleft()\n",
    "        #         if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[0]) or grid[x][y] == '0':\n",
    "        #             continue\n",
    "        #         grid[x][y] = '0'\n",
    "        #         queue.append((x+1, y))\n",
    "        #         queue.append((x-1, y))\n",
    "        #         queue.append((x, y+1))\n",
    "        #         queue.append((x, y-1))\n",
    "\n",
    "        # if not grid:\n",
    "        #     return 0\n",
    "\n",
    "        # count = 0\n",
    "        # for i in range(len(grid)):\n",
    "        #     for j in range(len(grid[0])):\n",
    "        #         if grid[i][j] == '1':\n",
    "        #             count += 1\n",
    "        #             # dfs(grid, i, j)\n",
    "        #             bfs(grid, i, j)\n",
    "\n",
    "        # return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        def find(x) :\n",
    "            if p[x] != x :\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "        def union(x, y) : \n",
    "            px, py = find(x), find(y) \n",
    "            if px == py :\n",
    "                return \n",
    "            p[px] = py\n",
    "        leny = len(grid)\n",
    "        lenx = len(grid[0])\n",
    "        p = list(range(lenx * leny))\n",
    "        for i, row in enumerate(grid) :\n",
    "            for j, v in enumerate(row) :\n",
    "                if v == '1' :\n",
    "                    for a, b in [[0, -1], [-1, 0]] :\n",
    "                        x, y = i + a, j + b\n",
    "                        if 0 <= x < leny and 0 <= y < lenx and grid[x][y] == '1':\n",
    "                            union(i * lenx + j, x * lenx + y)\n",
    "        ans = 0\n",
    "        havesee = dict()\n",
    "        for i in range(lenx * leny) :\n",
    "            if find(i) not in havesee and grid[i // lenx][i % lenx] != '0':\n",
    "                havesee[p[i]] = 1\n",
    "                ans += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "    # def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        # 深度优先\n",
    "        # def dfs(grid, i, j):\n",
    "        #     if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == '0':\n",
    "        #         return\n",
    "        #     grid[i][j] = '0'\n",
    "        #     dfs(grid, i+1, j)\n",
    "        #     dfs(grid, i-1, j)\n",
    "        #     dfs(grid, i, j+1)\n",
    "        #     dfs(grid, i, j-1)\n",
    "\n",
    "        # 广度优先\n",
    "        # def bfs(grid, i, j):\n",
    "        #     queue = deque([(i, j)])\n",
    "        #     while queue:\n",
    "        #         x, y = queue.popleft()\n",
    "        #         if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[0]) or grid[x][y] == '0':\n",
    "        #             continue\n",
    "        #         grid[x][y] = '0'\n",
    "        #         queue.append((x+1, y))\n",
    "        #         queue.append((x-1, y))\n",
    "        #         queue.append((x, y+1))\n",
    "        #         queue.append((x, y-1))\n",
    "\n",
    "        # if not grid:\n",
    "        #     return 0\n",
    "\n",
    "        # count = 0\n",
    "        # for i in range(len(grid)):\n",
    "        #     for j in range(len(grid[0])):\n",
    "        #         if grid[i][j] == '1':\n",
    "        #             count += 1\n",
    "        #             # dfs(grid, i, j)\n",
    "        #             bfs(grid, i, j)\n",
    "\n",
    "        # return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        \n",
    "        res = 0\n",
    "\n",
    "        island = set()\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == '1':\n",
    "                    island.add((i, j))\n",
    "\n",
    "        while island:\n",
    "            c = list(island)[0]\n",
    "            island.remove(c)\n",
    "            start = deque([c])\n",
    "            res += 1\n",
    "            while start:\n",
    "                i, j = start.pop()\n",
    "                if (i-1, j) in island:\n",
    "                    start.append((i-1, j))\n",
    "                    island.remove((i-1, j))\n",
    "                if (i+1, j) in island:\n",
    "                    start.append((i+1, j))\n",
    "                    island.remove((i+1, j))\n",
    "                if (i, j-1) in island:\n",
    "                    start.append((i, j-1))\n",
    "                    island.remove((i, j-1))\n",
    "                if (i, j+1) in island:\n",
    "                    start.append((i, j+1))\n",
    "                    island.remove((i, j+1))\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "DIRECTIONS = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        if not grid or not grid[0]:\n",
    "            return 0\n",
    "        \n",
    "        n_row, n_col = len(grid), len(grid[0])\n",
    "        visited = set()\n",
    "        res = 0\n",
    "\n",
    "        for i in range(n_row):\n",
    "            for j in range(n_col):\n",
    "                if (i, j) in visited or grid[i][j] == '0':\n",
    "                    continue\n",
    "                self.bfs(grid, i, j, visited)\n",
    "                res += 1\n",
    "        \n",
    "        return res\n",
    "    \n",
    "\n",
    "    def bfs(self, grid, r, c, visited):\n",
    "        queue = deque([(r, c)])\n",
    "        visited.add((r, c))\n",
    "\n",
    "        while queue:\n",
    "            curr_r, curr_c = queue.popleft()\n",
    "            for dr, dc in DIRECTIONS:\n",
    "                new_r, new_c = curr_r + dr, curr_c + dc\n",
    "                if not self.is_valid(grid, new_r, new_c, visited):\n",
    "                    continue\n",
    "                visited.add((new_r, new_c))\n",
    "                queue.append((new_r, new_c))\n",
    "        return\n",
    "    \n",
    "\n",
    "    def is_valid(self, grid, r, c, visited):\n",
    "        if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):\n",
    "            return False\n",
    "        if (r, c) in visited:\n",
    "            return False\n",
    "        return grid[r][c] == '1'\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ret = 0\n",
    "        def dfs(i, j):\n",
    "            if grid[i][j] == '1':\n",
    "                grid[i][j] = '0'\n",
    "                for x, y in [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]:\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y] == '1':\n",
    "                        dfs(x, y)\n",
    "            return\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '1':\n",
    "                    dfs(i, j)\n",
    "                    ret += 1\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ret = 0\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if grid[i][j] == '1':\n",
    "                grid[i][j] = '0'\n",
    "                for x, y in [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]:\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y] == '1':\n",
    "                        dfs(x, y)\n",
    "            return\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '1':\n",
    "                    dfs(i, j)\n",
    "                    ret += 1\n",
    "        return ret\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.parent = {}\n",
    "\n",
    "    def find(self, x):\n",
    "        self.parent.setdefault(x, x)\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "        \n",
    "    def union_direct(self, x, y):\n",
    "        x_root, y_root = self.find(x), self.find(y)\n",
    "        if x_root <= y_root:\n",
    "            self.parent[y_root] = x_root\n",
    "\n",
    "    def add(self, x):\n",
    "        if x not in self.parent:\n",
    "            self.parent.setdefault(x, x)\n",
    "            \n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        uf = UnionFind()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                k = i * n + j\n",
    "                if grid[i][j] == '1':\n",
    "                    uf.add(k)\n",
    "                    if j > 0 and grid[i][j-1] == '1':\n",
    "                        uf.union_direct(k, k-1)\n",
    "                    if i > 0 and grid[i-1][j] == '1':\n",
    "                        uf.union_direct(k, k-n)\n",
    "                    if j < n - 1 and grid[i][j+1] == '1':\n",
    "                        uf.union_direct(k, k+1)\n",
    "                    if i < m - 1 and grid[i+1][j] == '1':\n",
    "                        uf.union_direct(k, k+n)\n",
    "        ret = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                k = i * n + j\n",
    "                if grid[i][j] == '1':\n",
    "                    ret.add(uf.find(k))\n",
    "        return len(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        num_row = len(grid)\n",
    "        num_col = len(grid[0])\n",
    "\n",
    "        id_matrix = [[(i, j) for j in range(num_col)] for i in range(num_row)]\n",
    "\n",
    "        def get_id(i, j):\n",
    "            id_ = id_matrix[i][j]\n",
    "            if id_ != (i, j):\n",
    "                id_ = get_id(*id_)\n",
    "                id_matrix[i][j] = id_\n",
    "            return id_\n",
    "        \n",
    "        for i in range(num_row):\n",
    "            for j in range(num_col):\n",
    "                if grid[i][j] == '0':\n",
    "                    id_matrix[i][j] = -1\n",
    "                    continue\n",
    "                \n",
    "                if i > 0 and grid[i - 1][j] == \"1\":\n",
    "                    id_matrix[i][j] = get_id(i - 1, j)\n",
    "                if j > 0 and grid[i][j - 1] == \"1\":\n",
    "                    id_ = get_id(i, j - 1)\n",
    "                    id_matrix[id_[0]][id_[1]] = get_id(i, j)\n",
    "        s = set()\n",
    "        for i in range(num_row):\n",
    "            for j in range(num_col):\n",
    "                if grid[i][j] == '0':\n",
    "                    continue\n",
    "                \n",
    "                id_ = get_id(i, j)\n",
    "                s.add(id_)\n",
    "        return len(s)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "        vis = set()\n",
    "\n",
    "        dx = [-1, 0, 1, 0]\n",
    "        dy = [0, 1, 0, -1]\n",
    "\n",
    "        def dfs(x, y):\n",
    "            grid[x][y] = '0'\n",
    "            vis.add(x * m + y)\n",
    "            for i in range(4):\n",
    "                a, b = x + dx[i], y + dy[i]\n",
    "                if a < 0 or a >= n or b < 0 or b >= m or grid[a][b] == '0':\n",
    "                    continue\n",
    "                if a * m + b in vis:\n",
    "                    continue\n",
    "                vis.add(a * m + b)\n",
    "                dfs(a, b)\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == '1':\n",
    "                    ans += 1\n",
    "                    dfs(i, j)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   \n",
    "    def numIslands(self, grid) -> int:\n",
    "        r = len(grid)\n",
    "        c = len(grid[0])\n",
    "        seen = set()\n",
    "        cnt = 0\n",
    "        \n",
    "        def dfs(i, j):\n",
    "            x = i * c + j\n",
    "            if i < 0 or i >= r or j < 0 or j >= c or (x in seen) or grid[i][j] == '0':\n",
    "                return\n",
    "            seen.add(x)\n",
    "            dfs(i-1, j)\n",
    "            dfs(i, j-1)\n",
    "            dfs(i+1, j)\n",
    "            dfs(i, j+1)\n",
    "\n",
    "        for ri in range(0, r):\n",
    "            for ci in range(0, c):\n",
    "                if (not ((ri * c + ci) in seen)) and grid[ri][ci] == '1':\n",
    "                    cnt = cnt + 1\n",
    "                    dfs(ri, ci)\n",
    "\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "\n",
    "        rows = len(grid)\n",
    "        lines = len(grid[0])\n",
    "\n",
    "        parent = [[[-1, -1] for i in range(lines)] for j in range(rows)]\n",
    "        for row in range(rows):\n",
    "            for line in range(lines):\n",
    "                if grid[row][line] == \"1\":\n",
    "                    parent[row][line] = [row, line]\n",
    "\n",
    "        def find_node(row: int, line: int):\n",
    "            if parent[row][line] != [row, line]:\n",
    "                parent[row][line] = find_node(parent[row][line][0], parent[row][line][1])\n",
    "            return parent[row][line]\n",
    "\n",
    "        def union_node(row1: int, line1: int, row2: int, line2: int):\n",
    "            p1 = find_node(row1, line1)\n",
    "            parent[p1[0]][p1[1]] = find_node(row2, line2)\n",
    "\n",
    "        for row in range(rows):\n",
    "            for line in range(lines):\n",
    "                if grid[row][line] == \"0\":\n",
    "                    continue\n",
    "                if line < lines - 1 and grid[row][line + 1] == \"1\":\n",
    "                    union_node(row, line, row, line + 1)\n",
    "                if row < rows - 1 and grid[row + 1][line] == \"1\":\n",
    "                    union_node(row, line, row + 1, line)\n",
    "\n",
    "        islands = 0\n",
    "        for row in range(rows):\n",
    "            for line in range(lines):\n",
    "                if grid[row][line] == \"1\" and parent[row][line] == [row, line]:\n",
    "                    islands += 1\n",
    "\n",
    "        return islands\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        f = {}\n",
    "\n",
    "        def find(x):\n",
    "            f.setdefault(x, x)\n",
    "            if f[x] != x:\n",
    "                f[x] = find(f[x])\n",
    "            return f[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            f[find(x)] = find(y)\n",
    "\n",
    "        if not grid: return 0\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == \"1\":\n",
    "                    for x, y in [[-1, 0], [0, -1]]:\n",
    "                        tmp_i = i + x\n",
    "                        tmp_j = j + y\n",
    "                        if 0 <= tmp_i < row and 0 <= tmp_j < col and grid[tmp_i][tmp_j] == \"1\":\n",
    "                            union(tmp_i * row + tmp_j, i * row + j)\n",
    "        # print(f)\n",
    "        res = set()\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == \"1\":\n",
    "                    res.add(find((i * row + j)))\n",
    "        return len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   \n",
    "    def numIslands(self, grid) -> int:\n",
    "        r = len(grid)\n",
    "        c = len(grid[0])\n",
    "        seen = dict()\n",
    "        cnt = 0\n",
    "        \n",
    "        def dfs(i, j):\n",
    "            x = i * c + j\n",
    "            if i < 0 or i >= r or j < 0 or j >= c or (x in seen) or grid[i][j] == '0':\n",
    "                return\n",
    "            seen[x] = True\n",
    "            dfs(i-1, j)\n",
    "            dfs(i, j-1)\n",
    "            dfs(i+1, j)\n",
    "            dfs(i, j+1)\n",
    "\n",
    "        for ri in range(0, r):\n",
    "            for ci in range(0, c):\n",
    "                if (not ((ri * c + ci) in seen)) and grid[ri][ci] == '1':\n",
    "                    cnt = cnt + 1\n",
    "                    dfs(ri, ci)\n",
    "\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid) -> int:    \n",
    "        def dfs(i,j):\n",
    "            visited.add((i,j))\n",
    "            for x_, y_ in dictions:\n",
    "                new_i, new_j = x_ + i, y_ + j\n",
    "                if 0 <= new_i < m and 0 <= new_j < n and grid[new_i][new_j] == '1' and (new_i, new_j) not in visited:\n",
    "                    # 走到下一步\n",
    "                    dfs(new_i, new_j)\n",
    "                    \n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        # 方向：上下左右\n",
    "        dictions = [(-1,0), (1,0), (0,-1), (0,1)]\n",
    "        visited = set()\n",
    "        \n",
    "        result = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if (i, j) not in visited and grid[i][j] == '1':\n",
    "                    dfs(i, j)\n",
    "                    result += 1\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def numIslands(self, grid: List[List[str]]) -> int:\n",
    "#         res = 0\n",
    "#         m = len(grid)\n",
    "#         n = len(grid[0])\n",
    "#         # 遍历 grid\n",
    "#         for i in range(m):\n",
    "#             for j in range(n):\n",
    "#                 if grid[i][j] == '1':\n",
    "#                     # 每发现一个岛屿，岛屿数量加一\n",
    "#                     res += 1\n",
    "#                     # 然后使用 DFS 将岛屿淹了\n",
    "#                     self.dfs(grid, i, j)\n",
    "#         return res\n",
    "\n",
    "#     # 从 (i, j) 开始，将与之相邻的陆地都变成海水\n",
    "#     def dfs(self, grid: List[List[str]], i: int, j: int) -> None:\n",
    "#         m = len(grid)\n",
    "#         n = len(grid[0])\n",
    "#         if i < 0 or j < 0 or i >= m or j >= n:\n",
    "#             # 超出索引边界\n",
    "#             return\n",
    "#         if grid[i][j] == '0':\n",
    "#             # 已经是海水了\n",
    "#             return\n",
    "#         # 将 (i, j) 变成海水\n",
    "#         grid[i][j] = '0'\n",
    "#         # 淹没上下左右的陆地\n",
    "#         self.dfs(grid, i + 1, j)\n",
    "#         self.dfs(grid, i, j + 1)\n",
    "#         self.dfs(grid, i - 1, j)\n",
    "#         self.dfs(grid, i, j - 1)\n",
    "class Solution:\n",
    "\t\tdef numIslands(self, grid: List[List[str]]) -> int:\n",
    "\t\t\tdef dfsMarkSeen(r, c) -> None:\n",
    "\t\t\t\tif (\n",
    "\t\t\t\t\tr not in range(rows)\n",
    "\t\t\t\t\tor c not in range(cols)\n",
    "\t\t\t\t\tor (r, c) in used\n",
    "\t\t\t\t\tor grid[r][c] == \"0\"\n",
    "\t\t\t\t\t):\n",
    "\t\t\t\t\treturn\n",
    "\t\t\t\tused.add((r, c))\n",
    "\t\t\t\tdirections = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "\t\t\t\tfor dx, dy in directions:\n",
    "\t\t\t\t\tdfsMarkSeen(r + dx, c + dy)\n",
    "\t\t\t\n",
    "\t\t\tif not grid or not grid[0]:\n",
    "\t\t\t\treturn 0\n",
    "\t\t\trows, cols = len(grid), len(grid[0])\n",
    "\t\t\tused = set()\n",
    "\t\t\tisland = 0\n",
    "\t\t\tfor r in range(rows):\n",
    "\t\t\t\tfor c in range(cols):\n",
    "\t\t\t\t\tif grid[r][c] == \"1\" and (r, c) not in used:\n",
    "\t\t\t\t\t\tisland += 1\n",
    "\t\t\t\t\t\tdfsMarkSeen(r, c)\n",
    "\t\t\treturn island\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\t\tdef numIslands(self, grid: List[List[str]]) -> int:\n",
    "\t\t\t\n",
    "\t\t\tdef inBound(r, c) -> bool:\n",
    "\t\t\t\treturn r in range(rows) and c in range(cols)\n",
    "\t\n",
    "\t\t\tdef dfsMarkSeen(r, c) -> None:\n",
    "\t\t\t\tif not inBound(r, c) or grid[r][c] == \"0\":\n",
    "\t\t\t\t\treturn\n",
    "\t\t\t\t# used.add((r, c))\n",
    "\t\t\t\tgrid[r][c] = \"0\"\n",
    "\t\t\t\tdirections = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "\t\t\t\tfor dx, dy in directions:\n",
    "\t\t\t\t\tdfsMarkSeen(r + dx, c + dy)\n",
    "\t\t\t\t\t\n",
    "\t\t\tif not grid or not grid[0]:\n",
    "\t\t\t\treturn 0\n",
    "\t\t\trows, cols = len(grid), len(grid[0])\n",
    "\t\t\tisland = 0\n",
    "\t\t\tfor r in range(rows):\n",
    "\t\t\t\tfor c in range(cols):\n",
    "\t\t\t\t\tif grid[r][c] == \"1\":\n",
    "\t\t\t\t\t\tisland += 1\n",
    "\t\t\t\t\t\tdfsMarkSeen(r, c)\n",
    "\t\t\treturn island\n",
    "\n",
    "class Solution:\n",
    "\tdef numIslands(self, grid: List[List[str]]) -> int:\n",
    "\t\tf = {}\n",
    "\n",
    "\t\tdef find(x):\n",
    "\t\t\tf.setdefault(x, x)\n",
    "\t\t\tif f[x] != x:\n",
    "\t\t\t\tf[x] = find(f[x])\n",
    "\t\t\treturn f[x]\n",
    "\n",
    "\t\tdef union(x, y):\n",
    "\t\t\tf[find(x)] = find(y)\n",
    "\t\t\t\n",
    "\t\tdef inBound(r, c) -> bool:\n",
    "\t\t\treturn r in range(rows) and c in range(cols)\n",
    "\n",
    "\t\tif not grid or not grid[0]:\n",
    "\t\t\treturn 0\n",
    "\t\trows, cols = len(grid), len(grid[0])\n",
    "\t\tfor r in range(rows):\n",
    "\t\t\tfor c in range(cols):\n",
    "\t\t\t\tif grid[r][c] == \"1\":\n",
    "\t\t\t\t\tfor x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:\n",
    "\t\t\t\t\t\tif inBound(x, y) and grid[x][y] == \"1\":\n",
    "\t\t\t\t\t\t\tunion((x, y), (r, c))\n",
    "\t\tres = set()\n",
    "\t\tfor r in range(rows):\n",
    "\t\t\tfor c in range(cols):\n",
    "\t\t\t\tif grid[r][c] == \"1\":\n",
    "\t\t\t\t\tres.add(find((r, c)))\n",
    "\t\t\t\t\t\n",
    "\t\treturn len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        visited = set()\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        dr = [-1, 0, 1, 0]\n",
    "        dc = [0, -1, 0, 1]\n",
    "        \n",
    "        def dfs(r, c):\n",
    "            visited.add((r,c))\n",
    "            for i in range(4):\n",
    "                nr, nc = r+dr[i], c+dc[i]\n",
    "                if 0<=nr<row and 0<=nc<col and grid[nr][nc] == '1' and (nr, nc) not in visited:\n",
    "                    dfs(nr, nc)\n",
    "\n",
    "        ans = 0 \n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == '1' and (i, j) not in visited:\n",
    "                    ans += 1\n",
    "                    dfs(i, j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def numIslands(self, grid: List[List[str]]) -> int:\n",
    "#         res = 0\n",
    "#         m = len(grid)\n",
    "#         n = len(grid[0])\n",
    "#         # 遍历 grid\n",
    "#         for i in range(m):\n",
    "#             for j in range(n):\n",
    "#                 if grid[i][j] == '1':\n",
    "#                     # 每发现一个岛屿，岛屿数量加一\n",
    "#                     res += 1\n",
    "#                     # 然后使用 DFS 将岛屿淹了\n",
    "#                     self.dfs(grid, i, j)\n",
    "#         return res\n",
    "\n",
    "#     # 从 (i, j) 开始，将与之相邻的陆地都变成海水\n",
    "#     def dfs(self, grid: List[List[str]], i: int, j: int) -> None:\n",
    "#         m = len(grid)\n",
    "#         n = len(grid[0])\n",
    "#         if i < 0 or j < 0 or i >= m or j >= n:\n",
    "#             # 超出索引边界\n",
    "#             return\n",
    "#         if grid[i][j] == '0':\n",
    "#             # 已经是海水了\n",
    "#             return\n",
    "#         # 将 (i, j) 变成海水\n",
    "#         grid[i][j] = '0'\n",
    "#         # 淹没上下左右的陆地\n",
    "#         self.dfs(grid, i + 1, j)\n",
    "#         self.dfs(grid, i, j + 1)\n",
    "#         self.dfs(grid, i - 1, j)\n",
    "#         self.dfs(grid, i, j - 1)\n",
    "class Solution:\n",
    "\t\tdef numIslands(self, grid: List[List[str]]) -> int:\n",
    "\t\t\tdef dfsMarkSeen(r, c) -> None:\n",
    "\t\t\t\tif (\n",
    "\t\t\t\t\tr not in range(rows)\n",
    "\t\t\t\t\tor c not in range(cols)\n",
    "\t\t\t\t\tor (r, c) in used\n",
    "\t\t\t\t\tor grid[r][c] == \"0\"\n",
    "\t\t\t\t\t):\n",
    "\t\t\t\t\treturn\n",
    "\t\t\t\tused.add((r, c))\n",
    "\t\t\t\tdirections = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "\t\t\t\tfor dx, dy in directions:\n",
    "\t\t\t\t\tdfsMarkSeen(r + dx, c + dy)\n",
    "\t\t\t\n",
    "\t\t\tif not grid or not grid[0]:\n",
    "\t\t\t\treturn 0\n",
    "\t\t\trows, cols = len(grid), len(grid[0])\n",
    "\t\t\tused = set()\n",
    "\t\t\tisland = 0\n",
    "\t\t\tfor r in range(rows):\n",
    "\t\t\t\tfor c in range(cols):\n",
    "\t\t\t\t\tif grid[r][c] == \"1\" and (r, c) not in used:\n",
    "\t\t\t\t\t\tisland += 1\n",
    "\t\t\t\t\t\tdfsMarkSeen(r, c)\n",
    "\t\t\treturn island"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        res = 0\n",
    "        not_visited = []\n",
    "        not_visited_dic = {}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '1':\n",
    "                    not_visited.append((i,j))\n",
    "                    not_visited_dic[(i,j)] = 1\n",
    "        def f(corr):\n",
    "            x, y = corr\n",
    "            if x+1 <= m-1 and grid[x+1][y] == '1' and (x+1,y) in not_visited_dic:\n",
    "                not_visited_dic.pop((x+1,y))\n",
    "                f((x+1,y))\n",
    "            if x-1 >= 0 and grid[x-1][y] == '1' and (x-1,y) in not_visited_dic:\n",
    "                not_visited_dic.pop((x-1,y))\n",
    "                f((x-1,y))\n",
    "            if y+1 <= n-1 and grid[x][y+1] == '1' and (x,y+1) in not_visited_dic:\n",
    "                not_visited_dic.pop((x,y+1))\n",
    "                f((x,y+1))\n",
    "            if y-1 >= 0 and grid[x][y-1] == '1' and (x,y-1) in not_visited_dic: \n",
    "                not_visited_dic.pop((x,y-1))\n",
    "                f((x,y-1))\n",
    "\n",
    "        while not_visited_dic:\n",
    "            curr = list(not_visited_dic.keys())[0]\n",
    "            not_visited_dic.pop(curr)\n",
    "            res += 1\n",
    "            f(curr)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        res = 0\n",
    "        not_visited = []\n",
    "        not_visited_dic = {}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '1':\n",
    "                    not_visited.append((i,j))\n",
    "                    not_visited_dic[(i,j)] = 1\n",
    "        def f(corr):\n",
    "            x, y = corr\n",
    "            if x+1 <= m-1 and grid[x+1][y] == '1' and (x+1,y) in not_visited_dic:\n",
    "                not_visited_dic.pop((x+1,y))\n",
    "                f((x+1,y))\n",
    "            if x-1 >= 0 and grid[x-1][y] == '1' and (x-1,y) in not_visited_dic:\n",
    "                not_visited_dic.pop((x-1,y))\n",
    "                f((x-1,y))\n",
    "            if y+1 <= n-1 and grid[x][y+1] == '1' and (x,y+1) in not_visited_dic:\n",
    "                not_visited_dic.pop((x,y+1))\n",
    "                f((x,y+1))\n",
    "            if y-1 >= 0 and grid[x][y-1] == '1' and (x,y-1) in not_visited_dic: \n",
    "                not_visited_dic.pop((x,y-1))\n",
    "                f((x,y-1))\n",
    "\n",
    "        while not_visited_dic:\n",
    "            curr = list(not_visited_dic.keys())[0]\n",
    "            not_visited_dic.pop(curr)\n",
    "            res += 1\n",
    "            f(curr)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        self.res=0\n",
    "        self.father={}\n",
    "        self.visited=[[0]*n for _ in range(m)]\n",
    "        self.countisland(grid)\n",
    "        return self.res\n",
    "         \n",
    "    def find(self,x,y):\n",
    "        if self.father[(x,y)]==(x,y):\n",
    "            return (x,y)\n",
    "        self.father[(x,y)]=self.find(self.father[(x,y)][0],self.father[(x,y)][1])\n",
    "        return self.father[(x,y)]\n",
    "    \n",
    "    def union(self,x1,y1,x2,y2):\n",
    "        #(x2,y2)连在(x1,y1)上\n",
    "        self.father[(x2,y2)]=self.find(x1,y1)\n",
    "    \n",
    "    def searchNode(self,x,y,grid):\n",
    "        for i,j in [[0,1],[0,-1],[1,0],[-1,0]]:\n",
    "            if x+i>=0 and x+i<len(grid) and y+j>=0 and y+j<len(grid[0]) and self.visited[x+i][y+j]==0 and grid[x+i][y+j]!='0':\n",
    "                self.visited[x+i][y+j]=1\n",
    "                self.union(x,y,x+i,y+j)\n",
    "                self.searchNode(x+i, y+j,grid)\n",
    "\n",
    "    def countisland(self,grid):\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j]=='1':\n",
    "                    self.father[(i,j)]=(i,j)\n",
    "\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j]=='1' and self.father[(i,j)]==(i,j):\n",
    "                    self.res+=1\n",
    "                    self.visited[i][j]=1\n",
    "                    self.searchNode(i,j,grid)\n",
    "                else:\n",
    "                    self.visited[i][j]=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands(self, grid: List[List[str]]) -> int:\n",
    "        count = 0\n",
    "        used = [[False] * len(grid[0]) for _ in range(len(grid))]\n",
    "        dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        def dfs(i, j):\n",
    "            used[i][j] = True\n",
    "            for dx, dy in dir:\n",
    "                x, y = i+dx, j+dy\n",
    "                if x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0]) and (not used[x][y]) and grid[x][y]=='1':\n",
    "                    dfs(x, y)\n",
    "            \n",
    "        for i in range(0, len(grid)):\n",
    "            for j in range(0, len(grid[0])):\n",
    "                if not used[i][j] and grid[i][j]=='1':\n",
    "                    count += 1\n",
    "                    dfs(i, j)\n",
    "        # print(used)\n",
    "        return count"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
